oj.uz

Submission #1113972

# Submission time Handle Problem Language Result Execution time Memory
1113972 2024-11-18T01:26:12 Z spycoderyt Synchronization (JOI13_synchronization) C++17
100 / 100
 570 ms 37980 KB 
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 3e5+5;
int st[N],in[N],out[N],p[33][N],fen[N],dp[2][N],child[N],dep[N];
vector<int> A[N];
int cnt = 1;
int n,m,q,a,b,x;
void add(int pos,int val) {
    for(int i = pos;i<N;i+=i&-i) fen[i]+=val;
}
int qry(int pos) {
    if(!pos)return 0;
    int res = 0;
    for(int i = pos;i>0;i-=i&-i) res += fen[i];
    return res;
}
void dfs(int u,int par = -1) {
    in[u]=cnt++;
    for(auto nxt : A[u])if(nxt!=par) {
        dep[nxt] = dep[u]+1;
        dfs(nxt,u);
        p[0][nxt] = u;
    }
    out[u]=cnt;
}
void dolca() {
    for(int i = 1;i<32;i++) {
        for(int j = 1;j<=n;j++) p[i][j] = p[i-1][p[i-1][j]];
    }
}
int fp(int x) {
    for(int i = 31;i>=0;i--) {
        if(p[i][x] && qry(in[p[i][x]]) == qry(in[x]))x=p[i][x];
    }
    return x;
}
int main() {
    cin>>n>>m>>q;
    vector<pair<int,int> > tmp;
    for(int i = 0;i<n-1;i++) {
        cin>>a>>b;
        A[a].push_back(b);A[b].push_back(a);
        tmp.push_back({a,b});
    }
    dfs(1);
    p[0][1] = 1;
    dolca();
    for(int i = 0;i<n-1;i++) {
        if(dep[tmp[i].f] < dep[tmp[i].s]) swap(tmp[i].f,tmp[i].s);
        child[i+1] = tmp[i].f;
    }
    for(int i = 1;i<=n;i++) add(in[i],1),add(out[i],-1),dp[0][i]=1;
    // for(int i = 1;i<=n;i++)cerr<<qry(i)-qry(i-1)<< " ";
    // cerr<<"\n";
    for(int i = 0;i<m;i++) {
        cin>>x;
        x = child[x];
        st[x] = 1-st[x];
        if(st[x]) {
            //turn on
            int anc = fp(p[0][x]);
            // cerr << x << " " << anc << "\n";
            add(in[x],-1),add(out[x],1);
            dp[0][anc] += dp[0][x] - dp[1][x];
        } else {
            // turn off
            int anc = fp(x);
            // cerr << x << " " << anc << "\n";
            add(in[x],1),add(out[x],-1);
            dp[0][x] = dp[1][x] = dp[0][anc];
        }
    }
    for(int i = 0;i<q;i++) {
        cin>>x;
        // if(st[x]) {
        //     st[x] = 1-st[x];
        //     int anc = fp(p[0][x]);
        //     add(in[x],1),add(out[x]+1,-1);
        //     dp[0][x] = dp[1][x] = dp[0][anc];
        // }
        // cout << dp[0][x] << "\n";
        // cerr << x << " " << fp(x) << "\n";
        cout << dp[0][fp(x)] << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7760 KB Output is correct
2 Correct 6 ms 7760 KB Output is correct
3 Correct 6 ms 7760 KB Output is correct
4 Correct 6 ms 7760 KB Output is correct
5 Correct 6 ms 7692 KB Output is correct
6 Correct 7 ms 7760 KB Output is correct
7 Correct 25 ms 9824 KB Output is correct
8 Correct 25 ms 9808 KB Output is correct
9 Correct 26 ms 9900 KB Output is correct
10 Correct 267 ms 29628 KB Output is correct
11 Correct 271 ms 29588 KB Output is correct
12 Correct 316 ms 37308 KB Output is correct
13 Correct 159 ms 29420 KB Output is correct
14 Correct 172 ms 28604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 30908 KB Output is correct
2 Correct 163 ms 32444 KB Output is correct
3 Correct 164 ms 34748 KB Output is correct
4 Correct 149 ms 34748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7760 KB Output is correct
2 Correct 6 ms 7656 KB Output is correct
3 Correct 7 ms 7760 KB Output is correct
4 Correct 7 ms 7760 KB Output is correct
5 Correct 6 ms 7612 KB Output is correct
6 Correct 14 ms 8272 KB Output is correct
7 Correct 46 ms 10320 KB Output is correct
8 Correct 570 ms 35320 KB Output is correct
9 Correct 557 ms 35192 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 37052 KB Output is correct
2 Correct 407 ms 35004 KB Output is correct
3 Correct 395 ms 35248 KB Output is correct
4 Correct 394 ms 35264 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7760 KB Output is correct
2 Correct 7 ms 7772 KB Output is correct
3 Correct 6 ms 7576 KB Output is correct
4 Correct 6 ms 7760 KB Output is correct
5 Correct 10 ms 7888 KB Output is correct
6 Correct 44 ms 9808 KB Output is correct
7 Correct 448 ms 30364 KB Output is correct
8 Correct 501 ms 37980 KB Output is correct
9 Correct 342 ms 30636 KB Output is correct
10 Correct 339 ms 29884 KB Output is correct
11 Correct 350 ms 34244 KB Output is correct
12 Correct 350 ms 34320 KB Output is correct
13 Correct 402 ms 37564 KB Output is correct