oj.uz

Submission #374096

# Submission time Handle Problem Language Result Execution time Memory
374096 2021-03-06T15:38:13 Z BartolM Synchronization (JOI13_synchronization) C++17
0 / 100
 70 ms 39148 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]];
        }
    }
}

int update(int x, int val) {
    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[node][i];
        if (curr && 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 'int update(int, int)':
synchronization.cpp:43:1: warning: no return statement in function returning non-void [-Wreturn-type]
   43 | }
      | ^
synchronization.cpp: In function 'void solve()':
synchronization.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
synchronization.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
synchronization.cpp: In function 'void load()':
synchronization.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 5484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 35176 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 5484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 39148 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 5484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -