oj.uz

Submission #877720

# Submission time Handle Problem Language Result Execution time Memory
877720 2023-11-23T13:14:39 Z hafo Synchronization (JOI13_synchronization) C++14
100 / 100
 326 ms 37008 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, m, q, u, v, x, st[maxn], en[maxn], timer = 0, cnt[maxn], last[maxn];
vector<int> g[maxn];
pa ed[maxn];
bool active[maxn];

struct BIT {
    int bit[maxn];

    void update(int x, int val) {
        for(; x <= n; x += x&-x) bit[x] += val;
    }
    
    int get(int x) {
        int ans = 0;
        for(; x; x -= x&-x) ans += bit[x];
        return ans;
    }

} bit;

struct LCA {
    int p[LOG][maxn], dep[maxn];

    void dfs(int u, int par) {
        p[0][u] = par;
        for(auto v:g[u]) {
            if(v == par) continue;
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
    }

    void init() {
        dep[1] = 0;
        dfs(1, 0);
        for(int i = 1; i < LOG; i++) {
            for(int u = 1; u <= n; u++) p[i][u] = p[i - 1][p[i - 1][u]];
        }
    }

    int find_nxt(int u) {
        for(int i = LOG - 1; i >= 0; i--) {
            if(p[i][u] == 0) continue;
            if(bit.get(st[p[i][u]]) == bit.get(st[u])) u = p[i][u];
        }
        return u;
    }

} lca;

void dfs(int u, int par) {
    st[u] = ++timer;
    for(auto v:g[u]) {
        if(v == par) continue;
        dfs(v, u);
    }
    en[u] = timer;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>m>>q;
    for(int i = 1; i < n; i++) {
        cin>>ed[i].fi>>ed[i].se;
        g[ed[i].fi].pb(ed[i].se);
        g[ed[i].se].pb(ed[i].fi);
    }

    dfs(1, 0);
    lca.init();

    for(int i = 1; i <= n; i++) {
        cnt[i] = 1;
        bit.update(st[i], -1);
        bit.update(en[i] + 1, 1);
    }
    
    while(m--) {
        cin>>x;
        u = ed[x].fi, v = ed[x].se;
        if(st[u] > st[v]) swap(u, v);
        if(active[x]) {
            cnt[v] = last[v] = cnt[lca.find_nxt(u)];
            bit.update(st[v], -1);
            bit.update(en[v] + 1, 1);
        } else {
            bit.update(st[v], 1);
            bit.update(en[v] + 1, -1);
            cnt[lca.find_nxt(u)] += cnt[v] - last[v];
        }
        active[x] ^= 1;
    }

    while(q--) {
        cin>>x;
        cout<<cnt[lca.find_nxt(x)]<<"\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24924 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 4 ms 25008 KB Output is correct
5 Correct 3 ms 24924 KB Output is correct
6 Correct 4 ms 24924 KB Output is correct
7 Correct 12 ms 25692 KB Output is correct
8 Correct 12 ms 25692 KB Output is correct
9 Correct 12 ms 25688 KB Output is correct
10 Correct 131 ms 31572 KB Output is correct
11 Correct 112 ms 31380 KB Output is correct
12 Correct 207 ms 36196 KB Output is correct
13 Correct 53 ms 31432 KB Output is correct
14 Correct 74 ms 30804 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 33616 KB Output is correct
2 Correct 54 ms 33484 KB Output is correct
3 Correct 70 ms 35556 KB Output is correct
4 Correct 70 ms 35416 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24920 KB Output is correct
2 Correct 3 ms 24924 KB Output is correct
3 Correct 3 ms 25100 KB Output is correct
4 Correct 3 ms 24924 KB Output is correct
5 Correct 4 ms 25052 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 17 ms 26456 KB Output is correct
8 Correct 326 ms 37008 KB Output is correct
9 Correct 239 ms 36948 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 36840 KB Output is correct
2 Correct 108 ms 36692 KB Output is correct
3 Correct 109 ms 36580 KB Output is correct
4 Correct 120 ms 36792 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 24920 KB Output is correct
2 Correct 4 ms 24924 KB Output is correct
3 Correct 3 ms 24924 KB Output is correct
4 Correct 3 ms 24924 KB Output is correct
5 Correct 4 ms 25060 KB Output is correct
6 Correct 15 ms 25636 KB Output is correct
7 Correct 180 ms 32260 KB Output is correct
8 Correct 227 ms 36964 KB Output is correct
9 Correct 67 ms 32532 KB Output is correct
10 Correct 94 ms 32340 KB Output is correct
11 Correct 74 ms 34852 KB Output is correct
12 Correct 76 ms 34964 KB Output is correct
13 Correct 116 ms 36592 KB Output is correct