oj.uz

Submission #714095

# Submission time Handle Problem Language Result Execution time Memory
714095 2023-03-23T23:12:54 Z hackerbhaiya Synchronization (JOI13_synchronization) C++14
100 / 100
 2698 ms 48528 KB 
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll long long
// #define ll int
#define f(i,a,b) for(ll i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;a%=md;if(a==0)return 0;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

ll n,m,q,tt=1;
vector<vector<ll> > v,dp;
vector<ll> in,out,dis;

struct node
{
    ll val;
    node()
    {
        val=0;
    }
};

vector<ll> a,pw;
vector<node> t;

node merge(node a, node b)
{
    node ans;
    ans.val=(a.val+b.val);
    return ans;
}

void build(int id, int l, int r)
{
    if(l==r)
    {
        t[id].val=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(id<<1,l,mid),build(id<<1|1,mid+1,r);
    t[id]=merge(t[id<<1],t[id<<1|1]);
}

void update(int id, int l, int r, int pos, ll p)
{
    if(l>pos || r<pos)
        return;
    if(l==r)
    {
        t[id].val+=p;
        return;
    }
    int mid=(l+r)/2;
    update(id<<1,l,mid,pos,p),update(id<<1|1,mid+1,r,pos,p);
    t[id]=merge(t[id<<1],t[id<<1|1]);
}

node query(int id, int l, int r, int lq, int rq)
{
    node def_val;
    if(l>rq || r<lq)
        return def_val;
    if(l>=lq && r<=rq)
        return t[id];
    int mid=(l+r)/2;
    return merge(query(id<<1,l,mid,lq,rq),query(id<<1|1,mid+1,r,lq,rq));
}

const int N=21;
int kth_ancestor(int node, int k)
{
    f(i,0,N)
    {
        if(k&1)
            node=dp[node][i];
        k>>=1;
    }
    return node;
}
 
ll find(ll a)
{
    rf(i,N-1,0)
    {
        ll node=kth_ancestor(a,pw[i]),cur=query(1,1,tt,in[node]+1,in[a]).val;
        if(!cur)
            a=node;
    }
    return a;
}

void dfs(ll cur, ll par)
{
    dp[cur][0]=par,in[cur]=tt++;
    f(i,0,sz(v[cur]))
    {
        ll node=v[cur][i];
        if(node!=par)
        {
            dis[node]=1+dis[cur];
            dfs(node,cur);
        }
    }
    out[cur]=tt++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    f(ilu,1,z+1)
    {
        // cout<<"Case #"<<ilu<<": ";
        cin>>n>>m>>q;

        pw.rz(N,1),v.rz(n+1),in.rz(n+1),out.rz(n+1),dis.rz(n+1),dp.rz(n+1,vector<ll> (N));
        vector<array<ll,2> > ed;
        ed.pb({0,0});

        f(i,1,N)
            pw[i]=pw[i-1]*2LL;
        
        f(i,1,n)
        {
            ll l,r;
            cin>>l>>r;
            v[l].pb(r),v[r].pb(l),ed.pb({l,r});
        }

        dfs(1,1);
        f(j,1,N)
        {
            f(i,1,n+1)
                dp[i][j]=dp[dp[i][j-1]][j-1];
        }
        f(i,1,n)
        {
            if(in[ed[i][0]]>in[ed[i][1]])
                swap(ed[i][0],ed[i][1]);
        }
        a.rz(tt+1),t.rz(4*tt+69);
        f(i,2,n+1)
            a[in[i]]=1,a[out[i]]=-1;
        build(1,1,tt);

        vector<ll> last(n+1),val(n+1,1);
        vector<ll> active(n+1);
        f(i,0,m)
        {
            
            ll id;
            cin>>id;

            ll l=ed[id][0],r=ed[id][1];
            if(active[id])
            {
                ll x=find(r);
                val[r]=last[id]=val[x];
                update(1,1,tt,in[r],1),update(1,1,tt,out[r],-1);
            }
            else
            {
                ll x=find(l),y=find(r),tot=val[x]+val[y]-last[id];
                val[x]=last[id]=tot;
                update(1,1,tt,in[r],-1),update(1,1,tt,out[r],1);
            }
            active[id]^=1;
        }

        while(q--)
        {
            ll node;
            cin>>node;
            cout<<val[find(node)]<<"\n";
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 12 ms 596 KB Output is correct
7 Correct 153 ms 4304 KB Output is correct
8 Correct 180 ms 4304 KB Output is correct
9 Correct 163 ms 4304 KB Output is correct
10 Correct 2052 ms 40084 KB Output is correct
11 Correct 2037 ms 40080 KB Output is correct
12 Correct 2215 ms 45628 KB Output is correct
13 Correct 1477 ms 40252 KB Output is correct
14 Correct 1286 ms 40076 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1466 ms 43068 KB Output is correct
2 Correct 1438 ms 44452 KB Output is correct
3 Correct 1102 ms 47452 KB Output is correct
4 Correct 1076 ms 47436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 16 ms 724 KB Output is correct
7 Correct 207 ms 4884 KB Output is correct
8 Correct 2617 ms 45852 KB Output is correct
9 Correct 2531 ms 45904 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2553 ms 45856 KB Output is correct
2 Correct 1593 ms 45900 KB Output is correct
3 Correct 1605 ms 48528 KB Output is correct
4 Correct 1596 ms 48524 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 17 ms 724 KB Output is correct
6 Correct 204 ms 4320 KB Output is correct
7 Correct 2698 ms 40328 KB Output is correct
8 Correct 2446 ms 45856 KB Output is correct
9 Correct 1862 ms 40764 KB Output is correct
10 Correct 1590 ms 40760 KB Output is correct
11 Correct 1750 ms 43644 KB Output is correct
12 Correct 1711 ms 46268 KB Output is correct
13 Correct 1566 ms 48528 KB Output is correct