Submission #377025

#	Time	Username	Problem	Language	Result	Execution time	Memory
377025		BartolM	Synchronization (JOI13_synchronization)	C++17	100 / 100	641 ms	23532 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40