oj.uz

Submission #92568

# Submission time Handle Problem Language Result Execution time Memory
92568 2019-01-03T14:46:32 Z LittleFlowers__ Synchronization (JOI13_synchronization) C++14
100 / 100
 186 ms 20616 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 5 ms 5116 KB Output is correct
4 Correct 5 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 16 ms 6008 KB Output is correct
8 Correct 16 ms 6008 KB Output is correct
9 Correct 17 ms 6008 KB Output is correct
10 Correct 134 ms 15204 KB Output is correct
11 Correct 141 ms 15096 KB Output is correct
12 Correct 172 ms 19932 KB Output is correct
13 Correct 122 ms 15188 KB Output is correct
14 Correct 90 ms 14200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 17272 KB Output is correct
2 Correct 77 ms 16888 KB Output is correct
3 Correct 66 ms 18768 KB Output is correct
4 Correct 66 ms 18812 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5240 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 5 ms 5112 KB Output is correct
4 Correct 5 ms 5112 KB Output is correct
5 Correct 5 ms 5116 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 16 ms 6648 KB Output is correct
8 Correct 147 ms 20600 KB Output is correct
9 Correct 145 ms 20572 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 20572 KB Output is correct
2 Correct 85 ms 19984 KB Output is correct
3 Correct 89 ms 20100 KB Output is correct
4 Correct 91 ms 20088 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 5 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 7 ms 5240 KB Output is correct
6 Correct 19 ms 6108 KB Output is correct
7 Correct 186 ms 16220 KB Output is correct
8 Correct 167 ms 20616 KB Output is correct
9 Correct 140 ms 16184 KB Output is correct
10 Correct 137 ms 15480 KB Output is correct
11 Correct 106 ms 18168 KB Output is correct
12 Correct 106 ms 18260 KB Output is correct
13 Correct 90 ms 19960 KB Output is correct