oj.uz

Submission #1107465

# Submission time Handle Problem Language Result Execution time Memory
1107465 2024-11-01T09:16:18 Z doducanh Synchronization (JOI13_synchronization) C++14
30 / 100
 187 ms 27760 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[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<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++){
        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);
    }
    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);
            lc[j]=v[y[j]]=v[xj];
        }
        else{
            add(in[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
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 Incorrect 2 ms 14840 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 23368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 3 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 14684 KB Output is correct
6 Correct 3 ms 14928 KB Output is correct
7 Correct 13 ms 16056 KB Output is correct
8 Correct 180 ms 27720 KB Output is correct
9 Correct 187 ms 27760 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 27724 KB Output is correct
2 Correct 99 ms 27356 KB Output is correct
3 Correct 97 ms 27464 KB Output is correct
4 Correct 105 ms 27472 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Incorrect 2 ms 14672 KB Output isn't correct
4 Halted 0 ms 0 KB -