Submission #1083981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083981		underwaterkillerwhale	Synchronization (JOI13_synchronization)	C++17	20 / 100	1032 ms	262288 KiB

synchronization

#pragma GCC optimize("conserve-stack")
#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e5 + 7;
const int M = 1e5 + 7;
const int Mod = 1e9 + 7;
const ll INF = 1e18;
const ll BASE = 137;
const int szBL = 350;

int n, Q, K;
pii ed[N];
vector<int> ke[M];
int pid[N];
int pa[M], nC[M], high[M], par[M][25];
int Head[M], ein[M];

bool stt[M];

struct Node2 {
    Node2 *lc, *rc;
    int val;
    Node2 () {
        lc = rc = NULL;
        val = 0;
    }

    Node2 (int _val) {
        lc = rc = NULL;
        val = _val;
    }

    Node2 (Node2 *lcc, Node2 *rcc) {
        lc = lcc;
        rc = rcc;
        val = max(lcc->val, rcc->val);
    }
};

struct Node {
    Node *lc, *rc;
    int val;
    Node () {
        lc = rc = NULL;
        val = 0;
    }

    Node (int _val) {
        lc = rc = NULL;
        val = _val;
    }

    Node (Node *lcc, Node *rcc) {
        lc = lcc;
        rc = rcc;
        val = lcc->val & rcc->val;
    }
};

Node *croot[N];
Node2 *croot2[N];

struct Persistent_Segment_Tree {
    int m;

    Node *build (int l, int r) {
        if (l == r) return new Node();
        int mid = l + r >> 1;
        return new Node(build (l, mid), build (mid + 1, r));
    }

    void init (int n) {
        m = n;
        croot[0] = build(1, m);
    }

    Node *update (Node *curr, int l, int r, int pos) {
        if (l == r) {
            Node *cur = new Node(0);
            cur->val = curr->val ^ 1;
            return cur;
        }
        int mid = l + r >> 1;
        if (mid < pos)
            return new Node(curr->lc, update (curr->rc, mid + 1, r, pos));
        else
            return new Node(update (curr->lc, l, mid, pos), curr->rc);
    }

    int get (Node *curr, int l, int r, int u, int v) {
        if (l > v || r < u) return 1;
        if (l >= u && r <= v) return curr->val;
        int mid = l + r >> 1;
        return get (curr->lc, l, mid, u, v) & get (curr->rc, mid + 1, r, u, v);
    }

    void update (int pos) {
        static int n_root = 0;
        ++n_root;
        croot[n_root] = update (croot[n_root - 1], 1, m, pos);
    }

    int get (Node* rt, int u, int v ) {
        return get (rt, 1, m, u, v);
    }
}ST;

struct Persistent_Segment_Tree2 {
    int m;

    Node2 *build (int l, int r) {
        if (l == r) return new Node2(1);
        int mid = l + r >> 1;
        return new Node2(build (l, mid), build (mid + 1, r));
    }

    void init (int n) {
        m = n;
        croot2[0] = build(1, m);
    }

    Node2 *update (Node2 *curr, int l, int r, int pos, int val, bool typ) {
        if (l == r) {
            Node2 *cur = new Node2(0);
            if (typ == 1) {
                cur->val = val;
            }
            else {
                cur->val = curr->val + val;
            }
            return cur;
        }
        int mid = l + r >> 1;
        if (mid < pos)
            return new Node2(curr->lc, update (curr->rc, mid + 1, r, pos, val, typ));
        else
            return new Node2(update (curr->lc, l, mid, pos, val, typ), curr->rc);
    }

    int get (Node2 *curr, int l, int r, int pos) {
        if (l > pos || r < pos) return 0;
        if (l == r) return curr->val;
        int mid = l + r >> 1;
        return max(get (curr->lc, l, mid, pos), get (curr->rc, mid + 1, r, pos));
    }

    void update (int pos, int val, bool typ) {
        static int n_root = 0;
        ++n_root;
        croot2[n_root] = update (croot2[n_root - 1], 1, m, pos, val, typ);
    }

    int get (Node2 *rt, int pos) {
        return get (rt, 1, m, pos);
    }
}ST2;

void pdfs (int u, int p) {
    high[u] = high[p] + 1;
    pa[u] = p;
    par[u][0] = p;
    rep (i, 1, 20) par[u][i] = par[par[u][i - 1]][i - 1];
    nC[u] = 1;
    iter (&v, ke[u]) {
        if (v != p) {
            pdfs(v, u);
            nC[u] += nC[v];
        }
    }
}

void hld (int u, int p) {
    static int time_dfs = 0;
    Head[u] = p;
    ein[u] = ++time_dfs;
    int mxV = -1;
    iter (&v, ke[u]) if (v != pa[u] && (mxV == -1 || nC[v] > nC[mxV])) mxV = v;
    if (mxV != -1) hld(mxV, p);
    iter (&v, ke[u]) {
        if (v == pa[u] || v == mxV) continue;
        hld(v, v);
    }
}

int label (int state, int u) {
    while (u != 0) {
        bool cnc = ST.get(croot[state], ein[Head[u]], ein[u]);
        if (cnc == 0) {
            if (ST.get(croot[state], ein[u], ein[u]) == 0) return u;
            reb (i, 20, 0) {
                int cur = par[u][i];
                if (high[cur] >= high[Head[u]] && ST.get(croot[state], ein[cur], ein[u])) {
                    u = cur;
                }
            }
            return pa[u];
        }
        u = pa[Head[u]];
    }
}

int getVal (int state, int u) {
    return ST2.get(croot2[state], ein[label(state, u)]);
}

void Connect (int state, int p) {
    int u = ed[p].fs, v = ed[p].se;
    int prvid = pid[p];
    if (high[u] > high[v]) swap(u, v);
    int delta = getVal(state - 1, v);
    if (pid[p] != -1) {
        delta -= getVal(pid[p], v);
    }
//    cout << u <<" "<<v<<" "<<getVal(state - 1,u)<<" "<<getVal(state - 1, v)<< " " <<delta<<"\n";
    ST2.update (ein[label(state - 1, u)], delta, 0);
    ST.update (ein[v]);
}

void Detach (int state, int p) {
    int u = ed[p].fs, v = ed[p].se;
    if (high[u] > high[v]) swap(u, v);
    int delta = getVal(state - 1, u);
    ST2.update (ein[v], delta, 1);
    ST.update (ein[v]);
    pid[p] = state;
}

void solution () {

    cin >> n >> Q >> K;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ed[i] = MP(u, v);
        ke[u].pb(v);
        ke[v].pb(u);
    }
    pdfs(1, 0);
    hld(1, 1);

    ST.init(n);
    ST2.init(n);
    rep (i, 1, n) pid[i] = -1;

    rep (i, 1, Q) {
        int p;
        cin >> p;
        stt[p] ^= 1;
        if (stt[p] == 1) {
            Connect(i, p);
        }
        else {
            Detach(i, p);
        }
    }
    rep (i, 1, K) {
        int X;
        cin >> X;
        cout << getVal(Q, X) <<"\n";
    }
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +4
mình có muốn dùng mảng này không?
10 20 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
9
4
6
3
5
3
6
9
3
7
2
4
8
2
5
1
6
5
1
6
6




*/

Compilation message (stderr)

synchronization.cpp: In member function 'Node* Persistent_Segment_Tree::build(int, int)':
synchronization.cpp:86:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'Node* Persistent_Segment_Tree::update(Node*, int, int, int)':
synchronization.cpp:101:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'int Persistent_Segment_Tree::get(Node*, int, int, int, int)':
synchronization.cpp:111:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'Node2* Persistent_Segment_Tree2::build(int, int)':
synchronization.cpp:131:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'Node2* Persistent_Segment_Tree2::update(Node2*, int, int, int, int, bool)':
synchronization.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'int Persistent_Segment_Tree2::get(Node2*, int, int, int)':
synchronization.cpp:161:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In function 'void Connect(int, int)':
synchronization.cpp:226:9: warning: unused variable 'prvid' [-Wunused-variable]
  226 |     int prvid = pid[p];
      |         ^~~~~
synchronization.cpp: In function 'int label(int, int)':
synchronization.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
  218 | }
      | ^

• Subtask 1: 0 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40