Submission #714094

#	Time	Username	Problem	Language	Result	Execution time	Memory
714094		hackerbhaiya	Synchronization (JOI13_synchronization)	C++14	20 / 100	2785 ms	48836 KiB

synchronization

#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;
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,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;

        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)
        {
            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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40