oj.uz

Submission #843478

# Submission time Handle Problem Language Result Execution time Memory
843478 2023-09-04T03:23:31 Z Cookie Synchronization (JOI13_synchronization) C++14
100 / 100
 196 ms 22584 KB 
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const int mxn = 1e5 + 5;
const ll inf = 1e18;
int n, m, q;
vt<int>adj[mxn + 1];
int dep[mxn + 1], tin[mxn + 1], tout[mxn + 1], ans[mxn + 1], tt = 0;
bool on[mxn + 1];
int bit[mxn + 1], up[mxn + 1][18], u[mxn + 1], v[mxn + 1], last[mxn + 1];
void upd(int p, int v){
    while(p <= n + 1){
        bit[p] += v; p += p & (-p);
    }
}
int get(int p){
    int ans = 0;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
void dfs(int s, int pre){
    tin[s] = ++tt;
    for(auto i: adj[s]){
        if(i != pre){
            up[i][0] = s; dep[i] = dep[s] + 1;
            dfs(i, s);
        }
    }
    tout[s] = tt;
}
int get_root(int u){
    int ans = u;
    for(int i = 17; i >= 0; i--){
        if(up[ans][i] != 0 && get(tin[up[ans][i]]) == get(tin[u])){
            ans = up[ans][i];
        }
    }
    return(ans);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        cin >> u[i] >> v[i];
        adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
    }
    dfs(1, -1);
    for(int i = 1; i < 18; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    for(int i = 1; i <= n; i++){
        ans[i] = 1;
        if(i != 1){
            upd(tin[i], 1); upd(tout[i] + 1, -1);
        }
    }
    for(int i = 0; i < m; i++){
        int id; cin >> id;
        int nodeu = u[id], nodev = v[id];
        if(dep[nodeu] > dep[nodev])swap(nodeu, nodev);
        if(!on[id]){
            int rootu = get_root(nodeu);
            ans[rootu] += ans[nodev] - last[nodev];
            upd(tin[nodev], -1); upd(tout[nodev] + 1, 1);
        }else{
            ans[nodev] = last[nodev] = ans[get_root(nodeu)];
            upd(tin[nodev], 1); upd(tout[nodev] + 1, -1);
        }
        on[id] = !on[id];
    }
   
    while(q--){
        int x; cin >> x;
        cout << ans[get_root(x)] << "\n";
    }
    return(0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 9 ms 9308 KB Output is correct
8 Correct 9 ms 9304 KB Output is correct
9 Correct 9 ms 9304 KB Output is correct
10 Correct 92 ms 18512 KB Output is correct
11 Correct 92 ms 18512 KB Output is correct
12 Correct 139 ms 21584 KB Output is correct
13 Correct 48 ms 18380 KB Output is correct
14 Correct 65 ms 17744 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 19792 KB Output is correct
2 Correct 57 ms 19636 KB Output is correct
3 Correct 67 ms 20968 KB Output is correct
4 Correct 67 ms 21072 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 13 ms 9560 KB Output is correct
8 Correct 176 ms 22352 KB Output is correct
9 Correct 186 ms 22584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 22580 KB Output is correct
2 Correct 112 ms 22000 KB Output is correct
3 Correct 108 ms 22100 KB Output is correct
4 Correct 107 ms 22248 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8792 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8808 KB Output is correct
6 Correct 11 ms 9304 KB Output is correct
7 Correct 123 ms 19320 KB Output is correct
8 Correct 177 ms 22352 KB Output is correct
9 Correct 62 ms 19400 KB Output is correct
10 Correct 85 ms 19024 KB Output is correct
11 Correct 75 ms 21060 KB Output is correct
12 Correct 76 ms 21072 KB Output is correct
13 Correct 109 ms 22012 KB Output is correct