oj.uz

Submission #1107487

# Submission time Handle Problem Language Result Execution time Memory
1107487 2024-11-01T09:40:11 Z doducanh Synchronization (JOI13_synchronization) C++14
30 / 100
 202 ms 25676 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<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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 4 ms 14672 KB Output is correct
3 Correct 3 ms 14844 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 15060 KB Output is correct
7 Correct 12 ms 15276 KB Output is correct
8 Correct 10 ms 15184 KB Output is correct
9 Correct 10 ms 15184 KB Output is correct
10 Correct 91 ms 21240 KB Output is correct
11 Incorrect 101 ms 21064 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 22096 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 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 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 14 ms 15696 KB Output is correct
8 Correct 202 ms 25164 KB Output is correct
9 Correct 181 ms 25160 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 25104 KB Output is correct
2 Correct 98 ms 25416 KB Output is correct
3 Correct 98 ms 25672 KB Output is correct
4 Correct 98 ms 25676 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 Correct 2 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 13 ms 15456 KB Output is correct
7 Incorrect 114 ms 22080 KB Output isn't correct
8 Halted 0 ms 0 KB -