oj.uz

Submission #1083981

# Submission time Handle Problem Language Result Execution time Memory
1083981 2024-09-04T17:57:20 Z underwaterkillerwhale Synchronization (JOI13_synchronization) C++17
20 / 100
 1032 ms 262288 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 5 ms 10076 KB Output is correct
7 Correct 38 ms 30672 KB Output is correct
8 Correct 39 ms 30548 KB Output is correct
9 Correct 40 ms 30528 KB Output is correct
10 Correct 665 ms 258824 KB Output is correct
11 Correct 667 ms 258900 KB Output is correct
12 Runtime error 1032 ms 262288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 262144 KB Output is correct
2 Correct 426 ms 261572 KB Output is correct
3 Correct 294 ms 153616 KB Output is correct
4 Correct 283 ms 153472 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 5 ms 10076 KB Output is correct
7 Correct 58 ms 31364 KB Output is correct
8 Runtime error 924 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 913 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 5 ms 10220 KB Output is correct
6 Correct 50 ms 30604 KB Output is correct
7 Correct 781 ms 259668 KB Output is correct
8 Runtime error 930 ms 262144 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -