Cod sursa(job #2964175)

Utilizator lolismekAlex Jerpelea lolismek Data 12 ianuarie 2023 16:00:10
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.35 kb
/// incomplet
/// scris la scoala pt problema xormax(ioit runda3)
#include <iostream>
#include <vector>

#define int long long

using namespace std;

const int NMAX = 5e4;
const int LOGMAX = 32;

int n, q;
vector <int> adj[NMAX + 1];

struct Edge{
    int a, b, c;
}edges[NMAX + 1];

int level[NMAX + 1];

void dfs1(int nod, int parent){
    level[nod] = level[parent] + 1;
    for(int child : adj[nod]){
        if(child != parent){
            dfs1(child, nod);
        }
    }
}

int xor[NMAX + 1];
int cost[NMAX + 1];

void dfs2(int nod, int parent){
    xor[nod] = cost[nod] ^ xor[parent];
    for(int child : adj[nod]){
        if(child != parent){
            dfs2(child, nod);
        }
    }
}

struct Update{
    int Start;
    int End;

    Update(){
        Start = -1;
        End = -1;
    }
}updates[NMAX + 1];

namespace Trie{
    struct Node{
        Node *nxt[2];

        Node(){
            nxt[0] = NULL;
            nxt[1] = NULL;
        }
    };

    Node *root = new Node;

    void Insert(Node *node, int x, int pos){
        if(pos < 0){
            return;
        }

        bool bit = ((x & (1 << pos)) > 0);

        if(node->nxt[bit] == NULL){
            node->nxt[bit] = new Node;
        }

        Insert(node->nxt[bit], x, pos - 1);
    }

    void Delete(Node *node, int x, int pos){
        /// TODO: to implement this function!
    }

    int findXorMax(Node *node, int x, int pos){
        if(pos < 0){
            return 0;
        }

        bool targetBit = !((x & (1 << pos)) > 0);

        if(node->nxt[targetBit] != NULL){
            return targetBit * (1 << pos) + findXorMax(node->nxt[targetBit], x, pos - 1)
        }
        return !targetBit * (1 << pos) + findXorMax(node->nxt[!targetBit], x, pos - 1);
    }
};

namespace AINT{
    vector <int> aint[4 * NMAX + 1];

    void update(int nod, int st, int dr, int uSt, int uDr, int val){
        if(uSt <= st && dr <= uDr){
            aint[nod].push_back(val);
            return;
        }

        int mij = (st + dr) / 2;
        if(uSt <= mij){
            update(2 * nod, st, mij, uSt, uDr, val);
        }
        if(mij + 1 <= uDr){
            update(2 * nod + 1, mij + 1, dr, uSt, uDr, val);
        }
    }


};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;

    for(int i = 1; i <= n - 1; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back(b);
        adj[b].push_back(a);
        edges[i] = {a, b, c};
    }

    dfs1(1, 0);

    for(int i = 1; i <= n - 1; i++){
        if(level[edges[i].a] > level[edges[i].b]){
            cost[edges[i].a] = edges[i].c;
        }else{
            cost[edges[i].b] = edges[i].c;
        }
    }

    for(int i = 1; i <= q; i++){
        int x;
        cin >> x;

        if(updates[x].Start == -1){
            updates[x].Start = i;
        }else{
            updates[x].End = i;
        }
    }

    for(int i = 1; i <= n; i++){
        if(updates[i].Start != -1 && updates[i].End == -1){
            updates[i].End = n + 1;
        }
    }

    for(int i = 1; i <= n; i++){
        if(updates[i].Start != -1){
            AINT::update(1, 1, n + 1, updates[i].Start, updates[i].End, i);
        }
    }



    return 0;
}