Submission #92568

#	Time	Username	Problem	Language	Result	Execution time	Memory
92568		LittleFlowers__	Synchronization (JOI13_synchronization)	C++14	100 / 100	186 ms	20616 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
inline long long in(){long long x=0;char c=getchar();bool neg=false;while(c!='-'&&('0'>c||c>'9')) c=getchar();if(c=='-') neg=true,c=getchar();while('0'<=c&&c<='9') x=10*x+c-'0',c=getchar();if(neg) x=-x;return x;}
inline void out(long long x){if(x<0) putchar('-'),x=-x;if(x>9) out(x/10);putchar(x%10+'0');}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "SYNC"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define _ putchar(' ')
#define __ putchar('\n')
const int N=200010;
int n,m,q,it;
int x[N],y[N],st[N],ed[N],pos[N],h[N],ans[N],last[N],flip[N];
int t[4*N];
vector<int> ad[N];
void dfs(int u,int p)
{
    st[u]=++it,pos[it]=u;
    forv(v,ad[u]) if(v!=p)
        h[v]=h[u]+1,dfs(v,u);
    ed[u]=it;
}
#define goc 1,1,n
#define lef 2*s,l,mid
#define rig 2*s+1,mid+1,r
#define mid (l+r)/2
void build(int s,int l,int r)
{
    if(l==r)
    {
        t[s]=ed[pos[l]];
        return;
    }
    build(lef);
    build(rig);
    t[s]=max(t[2*s],t[2*s+1]);
}
void up(int s,int l,int r,int i,int x)
{
    if(l>i||i>r) return;
    if(l==r)
    {
        t[s]=x;
        return;
    }
    up(lef,i,x);
    up(rig,i,x);
    t[s]=max(t[2*s],t[2*s+1]);
}
int get(int s,int l,int r,int u,int v)
{
    if(l>u||t[s]<v) return -1;
    if(l==r) return l;
    int cur=get(rig,u,v);
    if(cur!=-1) return cur;
    return get(lef,u,v);
}
main()
{
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    n=in(),m=in(),q=in();
    forinc(i,1,n-1)
    {
        x[i]=in(),y[i]=in();
        ad[x[i]].pb(y[i]);
        ad[y[i]].pb(x[i]);
    }
    dfs(1,1);
    forinc(i,1,n) ans[i]=1;
    build(goc);
    forinc(i,1,n-1) if(h[x[i]]>h[y[i]]) swap(x[i],y[i]);
    forinc(i,1,m)
    {
        int o=in();
        if(!flip[o])
        {
            ans[pos[get(goc,st[x[o]],ed[x[o]])]]+=ans[y[o]]-last[o];
            up(goc,st[y[o]],0);
        }
        else
        {
            ans[y[o]]=last[o]=ans[pos[get(goc,st[x[o]],ed[x[o]])]];
            up(goc,st[y[o]],ed[y[o]]);
        }
        flip[o]^=1;
    }
    forinc(i,1,q)
    {
        int o=in();
        cout<<ans[pos[get(goc,st[o],ed[o])]]<<"\n";
    }
}

Compilation message (stderr)

synchronization.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40