Submission #205533

#	Time	Username	Problem	Language	Result	Execution time	Memory
205533		GioChkhaidze	Synchronization (JOI13_synchronization)	C++14	100 / 100	406 ms	18152 KiB

synchronization

#include <bits/stdc++.h>
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define F first
#define S second
using namespace std;
const int N=1e5+5;
int n,m,q,timer,depth;
int in[N],out[N],O[N],dep[N],ANS[N],last[N];
int v[8*N];
bool Bol[2*N];
vector < int > V[N];

void Dfs(int x,int p) {
    dep[x]=++depth;
    in[x]=++timer,O[in[x]]=x;
    for (int i=0; i<V[x].size(); i++) {
        int to=V[x][i];
        if (to!=p) Dfs(V[x][i],x);
    }
    out[x]=timer,--depth;
}

void Build(Tree) {
    if (l==r) {
        v[h]=out[O[l]];
        return ;
    }
    Build(Left),Build(Right);
    v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}

int idx,type;
void Upd(Tree) {
    if (idx<l || r<idx) return ;
    if (l==idx && r==idx) {
        if (type)
            v[h]=-1;
                else
            v[h]=out[O[l]];
        return ;
    }
    Upd(Left),Upd(Right);
    v[h]=max(v[(h<<1)],v[((h<<1)|1)]);
}

int L,R,D;
int Get(Tree) {
    if (r<L || R<l) return -1;
    if (l==r) {
        if (v[h]==-1) return -1;
        return O[l];
    }
    if (L<=l && r<=R) {
        int x=v[(h<<1)],y=v[((h<<1)|1)];
        if (R<=y) return Get(Right);
        return Get(Left);
    }
    int x=Get(Left),y=Get(Right);
    if (x==-1) return y;
    if (y==-1) return x;
    if (R<=out[y]) return y;
    if (R<=out[x]) return x;
    return -1;
}

main () {
    scanf("%d%d%d",&n,&m,&q);

    vector < pair < int , int > > edges;

    for (int i=1; i<n; i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        V[a].push_back(b);
        V[b].push_back(a);
        edges.push_back({a,b});
    }

    Dfs(1,1);
    Build(1,1,n);

    for (int i=1; i<=n; i++) ANS[i]=1;

    int x,a,b,delta,id;
    for (int i=1; i<=m; i++) {
        scanf("%d",&x); --x;
        a=edges[x].F,b=edges[x].S;
        if (dep[a]<dep[b]) swap(a,b);

        Bol[a]^=1;
        if (Bol[a]) {
            idx=in[a],type=1;
            Upd(1,1,n);
            L=1,R=in[a],id=Get(1,1,n);
            ANS[id]+=ANS[a]-last[a];
        }
            else
        if (!Bol[a]) {
            L=1,R=in[a],id=Get(1,1,n);
            last[a]=ANS[id];
            ANS[a]=ANS[id];
            idx=in[a],type=0;
            Upd(1,1,n);
        }
    }

    for (int i=1; i<=q; i++) {
        scanf("%d",&x);
        L=1,R=in[x],id=Get(1,1,n);
        printf("%d\n",ANS[id]);
    }
}

Compilation message (stderr)

synchronization.cpp: In function 'void Dfs(int, int)':
synchronization.cpp:18:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<V[x].size(); i++) {
                   ~^~~~~~~~~~~~
synchronization.cpp: In function 'int Get(int, int, int)':
synchronization.cpp:56:13: warning: unused variable 'x' [-Wunused-variable]
         int x=v[(h<<1)],y=v[((h<<1)|1)];
             ^
synchronization.cpp: At global scope:
synchronization.cpp:68:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:86:15: warning: unused variable 'delta' [-Wunused-variable]
     int x,a,b,delta,id;
               ^~~~~
synchronization.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
synchronization.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x); --x;
         ~~~~~^~~~~~~~~
synchronization.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

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