oj.uz

Submission #377011

# Submission time Handle Problem Language Result Execution time Memory
377011 2021-03-12T17:56:50 Z BartolM Synchronization (JOI13_synchronization) C++17
0 / 100
 613 ms 23548 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(R[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("%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:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
synchronization.cpp: In function 'void load()':
synchronization.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
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 Incorrect 2 ms 2796 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 20328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 613 ms 23548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
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 Incorrect 2 ms 2796 KB Output isn't correct
4 Halted 0 ms 0 KB -