oj.uz

Submission #577772

# Submission time Handle Problem Language Result Execution time Memory
577772 2022-06-15T08:49:54 Z Do_you_copy Synchronization (JOI13_synchronization) C++14
100 / 100
 315 ms 27020 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <int, int>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const int maxN = 1e5 + 1;
int n, m, q, cnt, k;
int lift[maxN][18];
int child[maxN];
bool open[maxN];
int newidx[maxN];
int last[maxN];
int ans[maxN];

struct TEdge{
    int u, v;
};

int a[maxN + 1];
TEdge e[maxN];

vector <int> adj[maxN];

int lastval;
void dfs(int u, int p, int deg){
    a[++cnt] = deg - lastval;
    newidx[u] = cnt;
    lastval = deg;
    lift[u][0] = max(1, p);
    for (int i = 1; i <= k; ++i){
        lift[u][i] = max(lift[lift[u][i - 1]][i - 1], 1);
    }
    for (const int &i: adj[u]){
        if (i != p){
            dfs(i, u, deg + 1);
            child[u] += child[i] + 1;
        }
    }
}

int bit[maxN];

void update(int i, int v){
    //binary indexed tree
    while (i <= n){
        bit[i] += v;
        i += i & (-i);
    }
}

int kid(int u, int v){
    return (child[u] > child[v]) ? v : u;
}

int get(int i){
    int tem = 0;
    while (i > 0){
        tem += bit[i];
        i -= i & (-i);
    }
    return tem;
}

int findancestor(int u){
    for (int i = k; i >= 0; --i){
        if (get(newidx[lift[u][i]]) == get(newidx[u])){
            u = lift[u][i];
        }
    }
    return u;
}

void Init(){
    cin >> n >> m >> q;
    fill (ans + 1, ans + n + 1, 1);
    k = log2(n) + 1;
    for (int i = 1; i < n; ++i){
        cin >> e[i].u >> e[i].v;
        adj[e[i].u].pb(e[i].v);
        adj[e[i].v].pb(e[i].u);
    }
    dfs(1, 0, 1);
    for (int i = 1; i <= n; ++i) update(i, a[i]);
    while (m--){
        int i; cin >> i;
        open[i] = !open[i];
        int v = kid(e[i].u, e[i].v);

        int l = newidx[v];
        int r = l + child[v];
        if (open[i]){
            update(l, -1);
            update(r + 1, 1);
            int p = findancestor(v);
            ans[p] += ans[v] - last[v];
        }
        else{
            int p = findancestor(v);
            update(l, 1);
            update(r + 1, -1);
            last[v] = ans[v] = ans[p];
        }
    }
    while (q--){
        int x; cin >> x; cout << ans[findancestor(x)] << "\n";
    }
}

int main(){
    if (fopen(taskname".txt", "r")){
        freopen(taskname".txt", "r", stdin);
    }
    faster
    //freopen(taskname.inp, "r", stdin)
    //freopen(taskname.out, "w", stdout)
    Init();
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(taskname".txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 2 ms 2828 KB Output is correct
7 Correct 15 ms 4180 KB Output is correct
8 Correct 15 ms 4252 KB Output is correct
9 Correct 15 ms 4180 KB Output is correct
10 Correct 236 ms 18472 KB Output is correct
11 Correct 244 ms 18464 KB Output is correct
12 Correct 243 ms 26176 KB Output is correct
13 Correct 112 ms 17880 KB Output is correct
14 Correct 139 ms 17564 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 19716 KB Output is correct
2 Correct 97 ms 21404 KB Output is correct
3 Correct 104 ms 25164 KB Output is correct
4 Correct 106 ms 25224 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 25 ms 5068 KB Output is correct
8 Correct 290 ms 26932 KB Output is correct
9 Correct 274 ms 26988 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 24064 KB Output is correct
2 Correct 166 ms 26300 KB Output is correct
3 Correct 194 ms 26460 KB Output is correct
4 Correct 164 ms 26468 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 2832 KB Output is correct
6 Correct 19 ms 4232 KB Output is correct
7 Correct 315 ms 19348 KB Output is correct
8 Correct 275 ms 27020 KB Output is correct
9 Correct 158 ms 19016 KB Output is correct
10 Correct 194 ms 18792 KB Output is correct
11 Correct 124 ms 23000 KB Output is correct
12 Correct 129 ms 22852 KB Output is correct
13 Correct 166 ms 26444 KB Output is correct