oj.uz

Submission #377025

# Submission time Handle Problem Language Result Execution time Memory
377025 2021-03-12T18:45:00 Z BartolM Synchronization (JOI13_synchronization) C++17
100 / 100
 641 ms 23532 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e5+5;
const int LOG=17;

int n, m, q, dtime=1;
vector <pii> ls[N];
int ed[N], par[LOG][N], L[N], R[N], akt[N];
int cnt_ed[N], cnt[N], F[2*N];

void dfs(int node, int rod, int br) {
    ed[br]=node;
    par[0][node]=rod;
    L[node]=dtime++;
    cnt[node]=1;
    for (pii sus:ls[node]) if (sus.X!=rod) dfs(sus.X, node, sus.Y);
    R[node]=dtime++;
}

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=1; j<=n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

void update(int x, int val) {
    assert(x);
    for (; x<=2*n; x+=x&-x) F[x]+=val;
}

int query(int x) {
    int ret=0;
    for (; x>0; x-=x&-x) ret+=F[x];
    return ret;
}

int parent(int node) {
    for (int i=LOG-1; i>=0; --i) {
        int curr=par[i][node];
        if (!curr) continue;
        if (query(L[node])-query(L[curr])==(1<<i)) node=curr;
    }
    return node;
}

void solve() {
    dfs(1, 0, 0);
    build();
    for (int i=0; i<m; ++i) {
        int x, a, b, uk;
        scanf("%d", &x);
        a=ed[x];
        b=par[0][a];
        b=parent(b);


        if (!akt[x]) {
            uk=cnt[a]+cnt[b]-cnt_ed[x];
            cnt[a]=cnt[b]=cnt_ed[x]=uk;
            update(L[a], 1); update(R[a], -1);
        }
        else {
            cnt_ed[x]=cnt[a]=cnt[b];
            update(L[a], -1); update(R[a], 1);
        }
        akt[x]^=1;
    }
    for (int i=0; i<q; ++i) {
        int x;
        scanf("%d", &x);
//        printf("parent: %d\n", parent(x));
        printf("%d\n", cnt[parent(x)]);
    }
}

void load() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i=0; i<n-1; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        ls[a].pb(mp(b, i+1));
        ls[b].pb(mp(a, i+1));
    }
}

int main() {
    load();
    solve();
    return 0;
}

Compilation message

synchronization.cpp: In function 'void solve()':
synchronization.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
synchronization.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
synchronization.cpp: In function 'void load()':
synchronization.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 15 ms 4332 KB Output is correct
8 Correct 15 ms 4332 KB Output is correct
9 Correct 15 ms 4332 KB Output is correct
10 Correct 309 ms 18648 KB Output is correct
11 Correct 299 ms 18796 KB Output is correct
12 Correct 547 ms 22764 KB Output is correct
13 Correct 94 ms 18400 KB Output is correct
14 Correct 191 ms 17900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 20412 KB Output is correct
2 Correct 96 ms 20200 KB Output is correct
3 Correct 118 ms 21996 KB Output is correct
4 Correct 123 ms 21996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 4 ms 2924 KB Output is correct
7 Correct 26 ms 4828 KB Output is correct
8 Correct 641 ms 23532 KB Output is correct
9 Correct 582 ms 23404 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 23532 KB Output is correct
2 Correct 192 ms 23148 KB Output is correct
3 Correct 188 ms 23148 KB Output is correct
4 Correct 190 ms 23148 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 2 ms 2796 KB Output is correct
3 Correct 2 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 4 ms 2924 KB Output is correct
6 Correct 20 ms 4460 KB Output is correct
7 Correct 344 ms 19384 KB Output is correct
8 Correct 621 ms 23436 KB Output is correct
9 Correct 125 ms 19692 KB Output is correct
10 Correct 245 ms 19180 KB Output is correct
11 Correct 134 ms 21560 KB Output is correct
12 Correct 138 ms 21480 KB Output is correct
13 Correct 192 ms 23276 KB Output is correct