oj.uz

Submission #1107488

# Submission time Handle Problem Language Result Execution time Memory
1107488 2024-11-01T09:42:01 Z doducanh Synchronization (JOI13_synchronization) C++14
100 / 100
 201 ms 27984 KB 
///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
const int maxn=1e5+7;
int lc[maxn];
int x[maxn],y[maxn];
int in[maxn],out[maxn];
vector<int>adj[maxn];
int t[2*maxn];
int p[25][maxn];
int v[maxn];
int n,m,q;
int cnt=0;
int get(int x)
{
    int res=0;
    for(;x;x-=(x&(-x)))res+=t[x];
    return res;
}
void add(int x,int val)
{
    for(;x<2*maxn;x+=(x&(-x)))t[x]+=val;
}
void dfs(int u,int par)
{
    in[u]=++cnt;
    for(int v:adj[u])if(v!=par){
        p[0][v]=u;
        dfs(v,u);
    }
    out[u]=++cnt;
}
int Find(int x)
{
    int u=x;
    int tmp=get(in[u]);
    for(int i=20;i>=0;i--)if(p[i][u]!=0&&get(in[p[i][u]])==tmp){
        u=p[i][u];
    }
    return u;
}
void sol(void){
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        lc[i]=0;
        cin>>x[i]>>y[i];
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    dfs(1,0);
    for(int i=1;i<=20;i++){
        for(int j=1;j<=n;j++){
            p[i][j]=p[i-1][p[i-1][j]];
        }
    }
    for(int i=1;i<=n;i++){
        v[i]=1;
        add(in[i],1);
        add(out[i],-1);
    }
    for(int i=1;i<n;i++){
        if(p[0][x[i]]==y[i])swap(x[i],y[i]);
    }
    for(int i=1;i<=m;i++){
        int j;
        cin>>j;
        int xj=Find(x[j]);
        if(lc[j]==-1){
            add(in[y[j]],1);
            add(out[y[j]],-1);
            lc[j]=v[y[j]]=v[xj];
        }
        else{
            add(in[y[j]],-1);
            add(out[y[j]],1);
            v[xj]+=(v[y[j]]-lc[j]);
            lc[j]=-1;
        }
    }
    while(q--){
        int x;
        cin>>x;
        cout<<v[Find(x)]<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
    while(t--){
        sol();
    }
    // you should actually read the stuff at the bottom
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 3 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 2 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Correct 9 ms 15184 KB Output is correct
8 Correct 10 ms 15184 KB Output is correct
9 Correct 9 ms 15184 KB Output is correct
10 Correct 93 ms 18768 KB Output is correct
11 Correct 107 ms 18760 KB Output is correct
12 Correct 157 ms 27392 KB Output is correct
13 Correct 50 ms 20928 KB Output is correct
14 Correct 63 ms 20556 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 22164 KB Output is correct
2 Correct 58 ms 23880 KB Output is correct
3 Correct 78 ms 26828 KB Output is correct
4 Correct 69 ms 26748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 2 ms 14672 KB Output is correct
6 Correct 3 ms 14928 KB Output is correct
7 Correct 15 ms 15876 KB Output is correct
8 Correct 201 ms 25116 KB Output is correct
9 Correct 188 ms 25160 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 25160 KB Output is correct
2 Correct 111 ms 25552 KB Output is correct
3 Correct 98 ms 25676 KB Output is correct
4 Correct 98 ms 25696 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 11 ms 15240 KB Output is correct
7 Correct 124 ms 19204 KB Output is correct
8 Correct 200 ms 27976 KB Output is correct
9 Correct 76 ms 22208 KB Output is correct
10 Correct 74 ms 21832 KB Output is correct
11 Correct 90 ms 25160 KB Output is correct
12 Correct 73 ms 25160 KB Output is correct
13 Correct 109 ms 27984 KB Output is correct