oj.uz

Submission #757449

# Submission time Handle Problem Language Result Execution time Memory
757449 2023-06-13T07:53:10 Z bgnbvnbv Synchronization (JOI13_synchronization) C++14
100 / 100
 516 ms 40992 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
// y tuong bai nay la luu root tai node cao nhat trong tplt
ll in[maxN],out[maxN],P[maxN][19];
int tg=0;
vector<pli>g[maxN];
ll h[maxN],pos[maxN];
void dfs(ll u,ll p)
{
    in[u]=++tg;
    P[u][0]=p;
    for(int i=1;i<=18;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(auto zz:g[u])
    {
        if(zz.fi!=p)
        {
            h[zz.fi]=h[u]+1;
            pos[zz.se]=zz.fi;
            dfs(zz.fi,u);
        }
    }
    out[u]=tg;
}
ll n,bit[maxN];
void upd(ll u,ll val)
{
    ll i=in[u];
    while(i<=n)
    {
        bit[i]+=val;
        i+=(i&(-i));
    }
    i=out[u]+1;
    while(i<=n)
    {
        bit[i]-=val;
        i+=i&(-i);
    }
}
ll get(ll u)
{
    ll i=in[u];
    ll ans=0;
    while(i>0)
    {
        ans+=bit[i];
        i-=i&(-i);
    }
    return ans;
}
ll findp(ll u)
{
    ll v=u;
    for(int i=18;i>=0;i--)
    {
        ll x=P[u][i];
        if(get(v)-get(x)==h[v]-h[x]) u=x;
    }
    return u;
}
ll m,q,c[maxN];
ll a[maxN],b[maxN];
void solve()
{
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++) a[i]=1,c[i]=0;
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb({v,i});
        g[v].pb({u,i});
    }
    dfs(1,1);
    for(int i=1;i<=m;i++)
    {
        ll id;
        cin >> id;
        upd(pos[id],(c[id]^1)-c[id]);
        if(c[id]==0)
        {
            ll v=pos[id];
            //ll u=P[v][0];
            ll u=findp(v);
            a[u]=a[u]+a[v]-b[v];
            a[v]=0;
        }
        else
        {
            ll v=pos[id];
            a[v]=a[findp(P[v][0])];
            b[v]=a[findp(P[v][0])];
        }
        c[id]^=1;
    }
    //cout << get(4)-get(2)<<' '<<h[4]-h[2]<<'\n';
    for(int i=1;i<=q;i++)
    {
        ll x;
        cin >> x;
        cout << a[findp(x)]<<'\n';
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct
4 Correct 4 ms 7376 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 6 ms 7636 KB Output is correct
7 Correct 25 ms 10072 KB Output is correct
8 Correct 22 ms 10024 KB Output is correct
9 Correct 24 ms 10068 KB Output is correct
10 Correct 333 ms 34580 KB Output is correct
11 Correct 305 ms 34580 KB Output is correct
12 Correct 413 ms 40228 KB Output is correct
13 Correct 210 ms 34500 KB Output is correct
14 Correct 180 ms 33228 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 36496 KB Output is correct
2 Correct 110 ms 36140 KB Output is correct
3 Correct 139 ms 38840 KB Output is correct
4 Correct 159 ms 38880 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7444 KB Output is correct
2 Correct 6 ms 7352 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7456 KB Output is correct
6 Correct 8 ms 7764 KB Output is correct
7 Correct 29 ms 10768 KB Output is correct
8 Correct 456 ms 40944 KB Output is correct
9 Correct 441 ms 40960 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 40992 KB Output is correct
2 Correct 198 ms 39820 KB Output is correct
3 Correct 204 ms 40124 KB Output is correct
4 Correct 210 ms 40012 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7324 KB Output is correct
2 Correct 6 ms 7384 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 6 ms 7380 KB Output is correct
5 Correct 7 ms 7608 KB Output is correct
6 Correct 29 ms 10148 KB Output is correct
7 Correct 433 ms 35328 KB Output is correct
8 Correct 441 ms 40980 KB Output is correct
9 Correct 226 ms 35400 KB Output is correct
10 Correct 259 ms 34500 KB Output is correct
11 Correct 163 ms 37720 KB Output is correct
12 Correct 158 ms 37660 KB Output is correct
13 Correct 245 ms 40088 KB Output is correct