Submission #1161127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161127		knhatdev	Synchronization (JOI13_synchronization)	C++20	100 / 100	221 ms	59452 KiB

synchronization

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define task ""
using namespace std;

const int N = 1e6 + 5, mod = 1e9 + 7;
int n, m, q, tin[N], tout[N], Time;
ii a[N];
vector<int> g[N];
int h[N], up[N][25], bit[N], del[N];
int ans[N];
bool check[N];

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

void uprange(int u, int val){
    // cout << u << ' ' << tin[u] << ' ' << tout[u] << ' ' << val << '\n';
    update(tin[u], val);
    update(tout[u] + 1, -val);
}
void dfs(int u, int par){
    ans[u] = 1;
    tin[u] = ++Time;
    for(int v : g[u]){
        if(v == par) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        dfs(v, u);
    }
    tout[u] = Time;
    uprange(u, 1);
}

void build_lca(){
    h[1] = 1;
    dfs(1, -1);
    for(int j = 1; j <= 20; j++){
        for(int i = 1; i <= n; i++){
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
}

int find_par(int u){
    int x = get(tin[u]);
    // cout << u << ' ';
    for(int j = 20; j >= 0; j--){
        if(get(tin[up[u][j]]) == x)
            u = up[u][j];
    }
    // cout << u << '\n';
    return u;
}


main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        a[i] = {u, v};
    }
    build_lca();
    for(int i = 1; i <= m; i++){
        int id; cin >> id;
        int u = a[id].fi, v = a[id].se;
        if(tin[u] > tin[v]) swap(u, v);
        if(!check[id]){
            check[id] = 1;
//            cout << u << ' ' << find_par(u) << '\n';
            ans[find_par(u)] += ans[v] - del[v];
            uprange(v, -1);
        } else {
            check[id] = 0;
            ans[v] = del[v] = ans[find_par(u)];
            uprange(v, 1);
        }
    }
    while(q--){
        int u; cin >> u;
        cout << ans[find_par(u)] << '\n';
    }
}

Compilation message (stderr)

synchronization.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main(){
      | ^~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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