oj.uz

Submission #153132

# Submission time Handle Problem Language Result Execution time Memory
153132 2019-09-12T14:42:26 Z georgerapeanu Synchronization (JOI13_synchronization) C++11
100 / 100
 425 ms 17912 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 1e5;

int n,m,q;
pair<int,int> edge[NMAX + 5];
vector<int> graph[NMAX + 5];
int fa[NMAX + 5];

int fst[NMAX + 5];
int lst[NMAX + 5];
int len;

int aint[4 * NMAX + 5];
bool used[NMAX + 5];

int dp[NMAX + 5];
int taken_father[NMAX + 5];
int lin[NMAX + 5];

void predfs(int nod,int tata){
    fst[nod] = ++len;
    lin[len] = nod;
    fa[nod] = tata;

    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }
        predfs(it,nod);
    }

    lst[nod] = len;
}

void build(int nod,int st,int dr){
    if(st == dr){
        aint[nod] = lst[lin[st]];
        return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);

    aint[nod] = max(aint[nod * 2],aint[nod * 2 + 1]);
}

int query(int nod,int st,int dr,int l,int r,int val){
    if(r < st || l > dr || aint[nod] < val){
        return 0;
    }

    if(l <= st && dr <= r){
        if(st == dr){
            return st;
        }
        else if(aint[2 * nod + 1] >= val){
            return query(nod * 2 + 1,(st + dr) / 2 + 1,dr,l,r,val);
        }
        else{
            return query(nod * 2,st,(st + dr) / 2,l,r,val);
        }
    }

    int mid = (st + dr) / 2;
    return max(query(nod * 2,st,mid,l,r,val),query(nod * 2 + 1,mid + 1,dr,l,r,val));
}

void update(int nod,int st,int dr,int pos,int val){
    if(dr < pos || st > pos){
        return ;
    }

    if(st == dr){
        aint[nod] = val;
        return ;
    }

    int mid = (st + dr) / 2;

    update(nod * 2,st,mid,pos,val);
    update(nod * 2 + 1,mid + 1,dr,pos,val);

    aint[nod] = max(aint[nod * 2],aint[nod * 2 + 1]);
}

inline int get_root(int nod){
    return lin[query(1,1,n,1,fst[nod],lst[nod])];
}

int main(){

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

    for(int i = 1;i < n;i++){
        scanf("%d %d",&edge[i].first,&edge[i].second);
        graph[edge[i].first].push_back(edge[i].second);
        graph[edge[i].second].push_back(edge[i].first);
    }

    for(int i = 1;i <= n;i++){
        dp[i] = 1;
        taken_father[i] = 0;
    }

    predfs(1,0);
    build(1,1,n);

    while(m--){
        int x;
        scanf("%d",&x);

        int ch = (edge[x].first == fa[edge[x].second] ? edge[x].second:edge[x].first);
        int root = get_root(fa[ch]);

        if(used[x] == false){
            dp[root] += dp[ch] - taken_father[ch];
            used[x] = true;
            update(1,1,n,fst[ch],0);
        }
        else{
            used[x] = false;
            dp[ch] = taken_father[ch] = dp[root];
            update(1,1,n,fst[ch],lst[ch]);
        }
    }

    while(q--){
        int x;
        scanf("%d",&x);
        printf("%d\n",dp[get_root(x)]);
    }

    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:99: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:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&edge[i].first,&edge[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
synchronization.cpp:136: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 4 ms 2684 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 24 ms 3620 KB Output is correct
8 Correct 24 ms 3704 KB Output is correct
9 Correct 24 ms 3580 KB Output is correct
10 Correct 326 ms 12616 KB Output is correct
11 Correct 322 ms 12536 KB Output is correct
12 Correct 318 ms 17240 KB Output is correct
13 Correct 206 ms 12392 KB Output is correct
14 Correct 200 ms 11912 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12536 KB Output is correct
2 Correct 131 ms 14560 KB Output is correct
3 Correct 115 ms 16488 KB Output is correct
4 Correct 116 ms 16492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 29 ms 4216 KB Output is correct
8 Correct 372 ms 17844 KB Output is correct
9 Correct 381 ms 17832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 14944 KB Output is correct
2 Correct 158 ms 17500 KB Output is correct
3 Correct 159 ms 17776 KB Output is correct
4 Correct 155 ms 17684 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2672 KB Output is correct
4 Correct 5 ms 2684 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 32 ms 3704 KB Output is correct
7 Correct 425 ms 13244 KB Output is correct
8 Correct 371 ms 17912 KB Output is correct
9 Correct 265 ms 13552 KB Output is correct
10 Correct 266 ms 13128 KB Output is correct
11 Correct 182 ms 15736 KB Output is correct
12 Correct 183 ms 15808 KB Output is correct
13 Correct 154 ms 17656 KB Output is correct