oj.uz

Submission #882185

# Submission time Handle Problem Language Result Execution time Memory
882185 2023-12-02T19:05:51 Z abcvuitunggio Synchronization (JOI13_synchronization) C++17
50 / 100
 8000 ms 36368 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,x[100001],y[100001],d,c,last[100001],s[100001],res[100001],tin[100001],tout[100001],t,p[100001][20],ft[100001][2];
vector <int> ke[100001];
void update(int i, int j, int val){
    for (;i<=n;i+=i&(-i))
        ft[i][j]+=val;
}
int get(int i, int j){
    int res=0;
    for (;i;i-=i&(-i))
        res+=ft[i][j];
    return res;
}
int get(int u){
    return get(tout[u],1)-get(tin[u]-1,1);
}
void dfs(int u, int par){
    tin[u]=++t;
    for (int v:ke[u])
        if (v!=par){
            p[v][0]=u;
            for (int i=1;i<20;i++)
                p[v][i]=p[p[v][i-1]][i-1];
            dfs(v,u);
        }
    tout[u]=t;
}
int f(int u){
    for (int i=19;i>=0;i--)
        if (p[u][i]&&get(tin[u],0)-get(tin[p[u][i]],0)==(1<<i))
            u=p[u][i];
    return u;
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int i=1;i<n;i++){
        cin >> x[i] >> y[i];
        ke[x[i]].push_back(y[i]);
        ke[y[i]].push_back(x[i]);
    }
    fill(res,res+n+1,1);
    dfs(1,1);
    for (int i=1;i<=n;i++){
        update(tin[i],1,1);
        if (i>1)
            update(tin[p[i][0]],1,-1);
    }
    for (int i=1;i<n;i++)
        if (x[i]=p[y[i]][0])
            swap(x[i],y[i]);
    while (m--){
        cin >> d;
        s[d]^=1;
        update(tin[x[d]],0,s[d]*2-1);
        update(tout[x[d]]+1,0,1-s[d]*2);
        int u=f(y[d]);
        if (s[d]){
            int val=get(x[d])-last[d];
            update(tin[y[d]],1,val);
            if (u!=1)
                update(tin[p[u][0]],1,-val);
            res[u]+=val;
            continue;
        }
        last[d]=get(x[d]);
        res[x[d]]=res[u];
    }
    while (q--){
        cin >> c;
        cout << res[f(c)] << '\n';
    }
}

Compilation message

synchronization.cpp: In function 'int32_t main()':
synchronization.cpp:52:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   52 |         if (x[i]=p[y[i]][0])
      |             ~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Execution timed out 8054 ms 8796 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 33228 KB Output is correct
2 Correct 90 ms 32988 KB Output is correct
3 Correct 100 ms 35272 KB Output is correct
4 Correct 98 ms 34896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8836 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 15 ms 12088 KB Output is correct
8 Correct 295 ms 36368 KB Output is correct
9 Correct 322 ms 36224 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 36360 KB Output is correct
2 Correct 151 ms 35924 KB Output is correct
3 Correct 162 ms 36180 KB Output is correct
4 Correct 154 ms 36204 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Execution timed out 8079 ms 8844 KB Time limit exceeded
5 Halted 0 ms 0 KB -