oj.uz

Submission #205533

# Submission time Handle Problem Language Result Execution time Memory
205533 2020-02-29T06:30:26 Z GioChkhaidze Synchronization (JOI13_synchronization) C++14
100 / 100
 406 ms 18152 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 9 ms 2808 KB Output is correct
7 Correct 26 ms 3704 KB Output is correct
8 Correct 25 ms 3704 KB Output is correct
9 Correct 25 ms 3704 KB Output is correct
10 Correct 313 ms 12520 KB Output is correct
11 Correct 305 ms 12528 KB Output is correct
12 Correct 258 ms 17332 KB Output is correct
13 Correct 249 ms 12388 KB Output is correct
14 Correct 186 ms 11628 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 14448 KB Output is correct
2 Correct 147 ms 14316 KB Output is correct
3 Correct 125 ms 16108 KB Output is correct
4 Correct 117 ms 16236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 8 ms 2808 KB Output is correct
7 Correct 31 ms 4344 KB Output is correct
8 Correct 304 ms 17900 KB Output is correct
9 Correct 298 ms 18152 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 17900 KB Output is correct
2 Correct 167 ms 17260 KB Output is correct
3 Correct 179 ms 17388 KB Output is correct
4 Correct 176 ms 17388 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 7 ms 2680 KB Output is correct
5 Correct 8 ms 2812 KB Output is correct
6 Correct 31 ms 3832 KB Output is correct
7 Correct 406 ms 13420 KB Output is correct
8 Correct 307 ms 17896 KB Output is correct
9 Correct 306 ms 13540 KB Output is correct
10 Correct 250 ms 12776 KB Output is correct
11 Correct 204 ms 15596 KB Output is correct
12 Correct 201 ms 15596 KB Output is correct
13 Correct 192 ms 17388 KB Output is correct