oj.uz

Submission #906747

# Submission time Handle Problem Language Result Execution time Memory
906747 2024-01-14T23:45:25 Z typ_ik Synchronization (JOI13_synchronization) C++17
100 / 100
 982 ms 38232 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 4 ms 15708 KB Output is correct
3 Correct 4 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 9 ms 15964 KB Output is correct
7 Correct 50 ms 16400 KB Output is correct
8 Correct 55 ms 16516 KB Output is correct
9 Correct 50 ms 16516 KB Output is correct
10 Correct 616 ms 32464 KB Output is correct
11 Correct 593 ms 32596 KB Output is correct
12 Correct 859 ms 37204 KB Output is correct
13 Correct 353 ms 32420 KB Output is correct
14 Correct 355 ms 31828 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 33484 KB Output is correct
2 Correct 435 ms 35160 KB Output is correct
3 Correct 362 ms 36436 KB Output is correct
4 Correct 384 ms 36744 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15704 KB Output is correct
2 Correct 4 ms 15708 KB Output is correct
3 Correct 5 ms 15720 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 5 ms 15708 KB Output is correct
6 Correct 10 ms 15964 KB Output is correct
7 Correct 79 ms 17020 KB Output is correct
8 Correct 970 ms 38200 KB Output is correct
9 Correct 982 ms 38084 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 974 ms 36688 KB Output is correct
2 Correct 520 ms 37656 KB Output is correct
3 Correct 480 ms 37708 KB Output is correct
4 Correct 514 ms 37816 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 5 ms 15708 KB Output is correct
3 Correct 5 ms 15708 KB Output is correct
4 Correct 5 ms 15708 KB Output is correct
5 Correct 9 ms 15964 KB Output is correct
6 Correct 64 ms 16592 KB Output is correct
7 Correct 700 ms 33364 KB Output is correct
8 Correct 929 ms 38232 KB Output is correct
9 Correct 418 ms 33576 KB Output is correct
10 Correct 423 ms 33396 KB Output is correct
11 Correct 520 ms 35924 KB Output is correct
12 Correct 530 ms 35764 KB Output is correct
13 Correct 477 ms 38024 KB Output is correct