Submission #906734

#	Time	Username	Problem	Language	Result	Execution time	Memory
906734		typ_ik	Synchronization (JOI13_synchronization)	C++17	0 / 100	1564 ms	262144 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;
}

int sum(int l, int r) {
    return sum(r) - (l ? sum(l - 1) : 0);
}

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

void change(int idx, int val) {
    add(idx, -sum(idx, idx));
    add(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;
}

int update(int v, int val) {
    change(tin[v], val);
    change(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, 0); 
            ans[find_parent(u)] = prev_time[idx];
            ans[find_parent(v)] = prev_time[idx];
        } else {
            int res = ans[find_parent(u)] + ans[find_parent(v)] - prev_time[idx];
            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: In function 'int update(int, int)':
synchronization.cpp:89:1: warning: no return statement in function returning non-void [-Wreturn-type]
   89 | }
      | ^
synchronization.cpp: At global scope:
synchronization.cpp:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main() {
      | ^~~~

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