Submission #906747

#	Time	Username	Problem	Language	Result	Execution time	Memory
906747		typ_ik	Synchronization (JOI13_synchronization)	C++17	100 / 100	982 ms	38232 KiB

synchronization

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std; 

const int N = 3e5 + 128;
const int LOG = 20;
vector <int> g[N];
pair <int, int> edges[N];
int n, m, q;
int lift[N][LOG], depth[N], tin[N], tout[N];
int timer = 0;
int t[N], ans[N];

int sum(int r) {
    int ans = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1)
        ans += t[r];
    return ans;
} 

void add(int idx, int val) {
    for (; idx < n; idx = idx | (idx + 1))
        t[idx] += val;
} 

void dfs(int v, int p = 1) {
    if (v != 1)
        depth[v] = depth[p] + 1;

    lift[v][0] = p;
    for (int b = 1; b < LOG; b++)
        lift[v][b] = lift[lift[v][b-1]][b-1];

    tin[v] = timer++;
    for (auto& to : g[v])
        if (to != p)
            dfs(to, v);
    tout[v] = timer - 1;
}

int lca(int u, int v) {
    if (depth[v] > depth[u])
        swap(u, v);
    int k = depth[u] - depth[v];
    for (int b = 0; b < LOG; b++)
        if ((k >> b) & 1)
            u = lift[u][b];
    if (u == v)
        return u;
    for (int b = LOG - 1; b >= 0; b--)
        if (lift[v][b] != lift[u][b])
            v = lift[v][b], u = lift[u][b];
    return lift[u][0];
}

int get(int x) {
    return sum(tin[x]);
}

int get(int u, int v) {
    return get(u) + get(v) - 2 * get(lca(u, v));
}

int find_parent(int v) {
    for (int b = LOG - 1; b >= 0; b--)
        if (get(lift[v][b], v) == (1 << b))
            v = lift[v][b];
    return v;
}

void update(int v, int val) { 
    add(tin[v], val);
    add(tout[v] + 1, -val);
} 

bool state[N];
int prev_time[N];

void solve() {
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        cin >> edges[i].first >> edges[i].second;
        g[edges[i].first].push_back(edges[i].second);
        g[edges[i].second].push_back(edges[i].first);
    }

    for (int i = 1; i <= n; i++)
        ans[i] = 1;

    dfs(1); 

    for (int i = 0; i < m; i++) {
        int idx;
        cin >> idx;

        int u = edges[idx].first, v = edges[idx].second;  
        if (depth[u] > depth[v])
            swap(u, v); 
        
        if (state[idx]) { 
            prev_time[idx] = ans[find_parent(u)];
            update(v, -1); 
            ans[find_parent(u)] = ans[find_parent(v)] = prev_time[idx]; 
        } else {
            int res = ans[find_parent(u)] + ans[find_parent(v)] - prev_time[idx];
            prev_time[idx] = 0;  
            update(v, 1);
            ans[find_parent(u)] = res;
        }

        state[idx] = !state[idx]; 
    }    

    for (int i = 0; i < q; i++) {
        int x;
        cin >> x; 
        cout << ans[find_parent(x)] << '\n';
    }
}

main() { 
    boost;  
    solve();
    return 0;
}

Compilation message (stderr)

synchronization.cpp:127:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  127 | main() {
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40