oj.uz

Submission #886037

# Submission time Handle Problem Language Result Execution time Memory
886037 2023-12-11T12:12:23 Z Zero_OP Synchronization (JOI13_synchronization) C++14
100 / 100
 339 ms 37204 KB 
#include<bits/stdc++.h>

using namespace std;

#define range(v) begin(v), end(v)
#define compact(v) v.erase(unique(range(v)), end(v))

template<class T> bool minimize(T& a, T b){
    if(a > b) return a = b, true;
    return false;
}

template<class T> bool maximize(T& a, T b){
    if(a < b) return a = b, true;
    return false;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int N = 2e5 + 5;

int n, m, q, tin[N], tout[N], lift[20][N], h[N], res[N], info[N], timerDFS;
vector<int> g[N];
pair<int, int> e[N];
bool actived[N];

void dfsEuler(int u, int e){
    tin[u] = ++timerDFS;
    res[u] = 1;
    for(int v : g[u]) if(v != e){
        h[v] = h[u] + 1;
        lift[0][v] = u;
        for(int i = 1; i <= 17; ++i){
            lift[i][v] = lift[i - 1][lift[i - 1][v]];
        }
        dfsEuler(v, u);
    }
    tout[u] = ++timerDFS;
}

int bit[N];
void update(int id, int val){
    for(; id <= timerDFS; id += id & (-id)){
        bit[id] += val;
    }
}

int query(int id){
    int s = 0;
    for(; id > 0; id -= id & (-id)){
        s += bit[id];
    }
    return s;
}

int binLift(int u){
    for(int i = 17; i >= 0; --i){
        if(h[u] - (1 << i) >= 0){
            int p = lift[i][u];
            if(h[u] - h[p] == query(tin[u]) - query(tin[p])){
                u = lift[i][u];
            }
        }
    }
    return u;
}

void Zero_OP(){
    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);
        e[i] = {u, v};
    }

    dfsEuler(1, 1);
    for(int i = 1; i < n; ++i){
        if(lift[0][e[i].first] == e[i].second){
            swap(e[i].first, e[i].second);
        }
    }

    while(m--){
        int pos; cin >> pos;

        int u = e[pos].first, v = e[pos].second, upper = binLift(u);

        if(actived[pos]){
            res[v] = info[pos] = res[upper];
            update(tin[v], -1);
            update(tout[v], 1);
        }
        else{
            res[upper] += res[v] - info[pos];
            update(tin[v], 1);
            update(tout[v], -1);
        }

        actived[pos] ^= 1;
    }

    while(q--){
        int u; cin >> u;
        u = binLift(u);
        cout << res[u] << '\n';
    }
}

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

    #define task "antuvu"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    Zero_OP();

    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 4 ms 22876 KB Output is correct
3 Correct 4 ms 23004 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 4 ms 23132 KB Output is correct
7 Correct 11 ms 23724 KB Output is correct
8 Correct 13 ms 23640 KB Output is correct
9 Correct 10 ms 23640 KB Output is correct
10 Correct 106 ms 30292 KB Output is correct
11 Correct 118 ms 30224 KB Output is correct
12 Correct 229 ms 36436 KB Output is correct
13 Correct 47 ms 30192 KB Output is correct
14 Correct 91 ms 29636 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 33364 KB Output is correct
2 Correct 58 ms 33468 KB Output is correct
3 Correct 78 ms 35936 KB Output is correct
4 Correct 80 ms 35800 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 3 ms 22876 KB Output is correct
3 Correct 4 ms 22876 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 3 ms 23004 KB Output is correct
6 Correct 4 ms 23132 KB Output is correct
7 Correct 21 ms 24504 KB Output is correct
8 Correct 287 ms 37204 KB Output is correct
9 Correct 244 ms 37204 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 37204 KB Output is correct
2 Correct 120 ms 36944 KB Output is correct
3 Correct 128 ms 36924 KB Output is correct
4 Correct 120 ms 36944 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22872 KB Output is correct
2 Correct 3 ms 23052 KB Output is correct
3 Correct 3 ms 22876 KB Output is correct
4 Correct 3 ms 22876 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 13 ms 23784 KB Output is correct
7 Correct 165 ms 31168 KB Output is correct
8 Correct 234 ms 37188 KB Output is correct
9 Correct 62 ms 31432 KB Output is correct
10 Correct 118 ms 31060 KB Output is correct
11 Correct 75 ms 34368 KB Output is correct
12 Correct 76 ms 34384 KB Output is correct
13 Correct 115 ms 37148 KB Output is correct