oj.uz

Submission #1083991

# Submission time Handle Problem Language Result Execution time Memory
1083991 2024-09-04T18:19:21 Z underwaterkillerwhale Synchronization (JOI13_synchronization) C++17
100 / 100
 555 ms 44672 KB 
#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 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[N];
int val[N];
map<pii, int> pVal;

int pa[N], nC[N], high[N], par[N][25];
int Head[N], ein[N];
int pid[N];

bool stt[N];

struct Segment_Tree {
    int m;
    bool st[N << 2];

    void init (int n) {
        m = n;
    }

    void update (int id, int l, int r, int pos) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id] ^= 1;
            return;
        }
        int mid = l + r >> 1;
        update (id << 1, l, mid, pos);
        update (id << 1 | 1, mid + 1, r, pos);
        st[id] = st[id << 1] & st[id << 1 | 1];
    }
    int get (int id, int l, int r, int u, int v) {
        if (l > v|| r < u) return 1;
        if (l >= u && r <= v) return st[id];
        int mid = l + r >> 1;
        return get (id << 1, l, mid, u, v) & get (id << 1 | 1, mid + 1, r, u, v);
    }

    void update (int pos) {
        update (1, 1, m, pos);
    }
    int get (int u, int v ) {
        return get (1, 1, m, u, v);
    }
}ST;

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 root (int u) {
    while (u != 0) {
        bool cnc = ST.get(ein[Head[u]], ein[u]);
        if (cnc == 0) {
            if (ST.get(ein[u], ein[u]) == 0) return u;
            reb (i, 20, 0) {
                int cur = par[u][i];
                if (high[cur] >= high[Head[u]] && ST.get(ein[cur], ein[u])) {
                    u = cur;
                }
            }
            return pa[u];
        }
        u = pa[Head[u]];
    }
    assert(0);
}

int getVal (int u) {
    return val[root(u)];
}

void Connect (int state, int p) {
    int u = ed[p].fs, v = ed[p].se;
    if (high[u] > high[v]) swap(u, v);
    int delta = val[v];
    if (pid[p] != -1) {
        delta -= pVal[{v, pid[p]}];
    }
//    cout << u <<" "<<v<<" "<<getVal(u)<<" "<<getVal(v)<<"\n";
    val[root(u)] += delta;
    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);
    pVal[{u, state}] = pVal[{v, state}] = val[v] = getVal(u);
    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);
    }
    rep (i, 1, n) val[i] = 1, pid[i] = -1;
    pdfs(1, 0);
    hld(1, 1);
    ST.init(n);
//    return;
    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(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?
100 0 150
4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13
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 'void Segment_Tree::update(int, int, int, int)':
synchronization.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int mid = l + r >> 1;
      |                   ~~^~~
synchronization.cpp: In member function 'int Segment_Tree::get(int, int, int, int, int)':
synchronization.cpp:61:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 1 ms 10684 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 17 ms 14120 KB Output is correct
8 Correct 17 ms 14172 KB Output is correct
9 Correct 19 ms 14168 KB Output is correct
10 Correct 257 ms 35412 KB Output is correct
11 Correct 234 ms 35408 KB Output is correct
12 Correct 388 ms 43744 KB Output is correct
13 Correct 169 ms 37580 KB Output is correct
14 Correct 121 ms 27548 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 35644 KB Output is correct
2 Correct 202 ms 35156 KB Output is correct
3 Correct 151 ms 32072 KB Output is correct
4 Correct 145 ms 32080 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10584 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 34 ms 14628 KB Output is correct
8 Correct 513 ms 44672 KB Output is correct
9 Correct 555 ms 44628 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 44548 KB Output is correct
2 Correct 319 ms 34896 KB Output is correct
3 Correct 359 ms 35040 KB Output is correct
4 Correct 326 ms 34900 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 21 ms 14036 KB Output is correct
7 Correct 269 ms 35796 KB Output is correct
8 Correct 476 ms 44624 KB Output is correct
9 Correct 182 ms 38704 KB Output is correct
10 Correct 183 ms 28832 KB Output is correct
11 Correct 261 ms 38552 KB Output is correct
12 Correct 257 ms 38568 KB Output is correct
13 Correct 324 ms 34896 KB Output is correct