33222023-02-25 14:33:01gortomiXORfa visszatércpp17Időlimit túllépés 28/1001.613s521828 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<pair<int, int> > > g;
vector<int> v;
void dfs(int n, int p)
{
    for(auto x : g[n])
    {
        int y = x.first, z = x.second;
        if(y != p)
        {
            v[y] = v[n] ^ z;
            dfs(y, n);
        }
    }
}
struct node
{
    int w;
    node *lc, *rc;
    node()
    {
        w = 0;
        lc = nullptr;
        rc = nullptr;
    }
    void extend()
    {
        if(lc == nullptr)
        {
            lc = new node();
            rc = new node();
        }
    }
    void upd(int k, int ind, int del)
    {
        w += del;
        if(ind == -1) return;
        extend();
        if((k >> ind) & 1) rc -> upd(k, ind - 1, del);
        else lc -> upd(k, ind - 1, del);
    }
    int get(int k, int ind)
    {
        if(ind == -1) return 0;
        extend();
        if((k >> ind) & 1)
        {
            if(lc -> w > 0) return lc -> get(k, ind - 1) + (1 << ind);
            else return rc -> get(k, ind - 1);
        }
        else
        {
            if(rc -> w > 0) return rc -> get(k, ind - 1) + (1 << ind);
            else return lc -> get(k, ind - 1);
        }
    }
};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    g.resize(n + 1);
    v.resize(n + 1);
    for(int i = 0; i < n - 1; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    dfs(1, 0);
    const int b = 300;
    vector<int> no(q);
    vector<int> act(n + 1, -1);
    vector<pair<int, int> > add;
    for(int i = 0; i < q; i++)
    {
        cin >> no[i];
        if(act[no[i]] == -1)
        {
            act[no[i]] = i;
        }
        else
        {
            add.push_back({act[no[i]], i - 1});
            act[no[i]] = -1;
        }
    }
    for(int i = 1; i <= n; i++) if(act[i] != -1) add.push_back({act[i], q - 1});
    node root = node();
    vector<node> trie(b, root);
    vector<int> maxi(b);
    vector<vector<int> > ins(q);
    for(auto x : add)
    {
        int l = x.first, r = x.second;
        int val = no[l];
        while(l % b != 0 && l <= r)
        {
            ins[l].push_back(val);
            l++;
        }
        while(l + b - 1 <= r)
        {
            trie[l / b].upd(v[val], 29, 1);
            maxi[l / b] = max(maxi[l / b], trie[l / b].get(v[val], 29));
            l += b;
        }
        while(l <= r)
        {
            ins[l].push_back(val);
            l++;
        }
    }
    for(int i = 0; i < q; i++)
    {
        int actb = i / b;
        int ans = maxi[actb];
        for(auto x : ins[i])
        {
            trie[actb].upd(v[x], 29, 1);
            ans = max(ans, trie[actb].get(v[x], 29));
        }
        cout << ans << "\n";
        for(auto x : ins[i]) trie[actb].upd(v[x], 29, -1);
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1836 KiB
2Elfogadva3ms2060 KiB
subtask211/11
3Elfogadva4ms2528 KiB
4Elfogadva3ms2580 KiB
5Elfogadva4ms2752 KiB
6Elfogadva4ms2860 KiB
7Elfogadva4ms3072 KiB
8Elfogadva4ms3408 KiB
9Elfogadva4ms3336 KiB
10Elfogadva4ms3516 KiB
11Elfogadva4ms3604 KiB
12Elfogadva4ms3648 KiB
13Elfogadva4ms3592 KiB
subtask30/13
14Elfogadva86ms20708 KiB
15Elfogadva123ms23460 KiB
16Időlimit túllépés1.567s124772 KiB
17Időlimit túllépés1.557s146548 KiB
18Időlimit túllépés1.572s137720 KiB
19Időlimit túllépés1.582s167104 KiB
20Időlimit túllépés1.552s140116 KiB
21Időlimit túllépés1.595s146492 KiB
22Elfogadva133ms24168 KiB
23Elfogadva123ms24268 KiB
subtask417/17
24Elfogadva75ms10496 KiB
25Elfogadva41ms8548 KiB
26Elfogadva112ms13392 KiB
27Elfogadva144ms15148 KiB
28Elfogadva174ms16468 KiB
29Elfogadva64ms10808 KiB
30Elfogadva85ms11540 KiB
31Elfogadva87ms11768 KiB
32Elfogadva68ms10652 KiB
33Elfogadva68ms10668 KiB
34Elfogadva68ms10764 KiB
35Elfogadva68ms10768 KiB
subtask50/59
36Futási hiba754ms521828 KiB
37Futási hiba630ms521820 KiB
38Futási hiba652ms521800 KiB
39Futási hiba638ms521776 KiB
40Futási hiba732ms521768 KiB
41Futási hiba651ms521676 KiB
42Futási hiba633ms521660 KiB
43Futási hiba615ms521660 KiB
44Futási hiba615ms521644 KiB
45Időlimit túllépés1.564s109492 KiB
46Időlimit túllépés1.582s237536 KiB
47Időlimit túllépés1.57s238116 KiB
48Időlimit túllépés1.613s254384 KiB
49Időlimit túllépés1.578s241176 KiB