oj.uz

Submission #440967

# Submission time Handle Problem Language Result Execution time Memory
440967 2021-07-03T18:50:27 Z Vladth11 Synchronization (JOI13_synchronization) C++14
100 / 100
 1312 ms 24440 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;
const ll LIMIT = 1000;

pii timp[NMAX];
int n;
int stamp;
int dp[NMAX][nr_of_bits + 1];
int cnt[NMAX];
int stare[NMAX];
pii edges[NMAX];
int last[NMAX];

class AIB{
public:
    int aib[NMAX + 1];
    void update(int x, int val){
        for(int i = x; i <= n; i += i&(-i))
            aib[i] += val;
    }
    int query(int x){
        int v = 0;
        if(x == 0)
            return 0;
        for(int i = x; i > 0; i -= i&(-i))
            v += aib[i];
        return v;
    }
}aib;

vector <int> v[NMAX];
int lvl[NMAX];

void DFS(int node, int p){
    dp[node][0] = p;
    lvl[node] = lvl[p] + 1;
    timp[node].first = ++stamp;
    for(auto x : v[node]){
        if(x == p)
            continue;
        DFS(x, node);
    }
    timp[node].second = stamp;
}

bool OK(int a, int b){
    int p = dp[a][0];
    int c = lvl[b] - lvl[p];
    int vb = aib.query(timp[b].first);
    int vp = aib.query(timp[p].first);
    return (vb - vp == c);
}

int root(int x){
    int pas = nr_of_bits, r = x;
    while(pas >= 0){
        int nxt = dp[r][pas];
        if(nxt != 0 && OK(nxt, x))
            r = nxt;
        pas--;
    }
    if(r != 1 && OK(r, x))
        r = dp[r][0];
    return r;
}

int val(int x){
    return cnt[root(x)];
}

void changeval(int x, int val){
    cnt[root(x)] = val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, m, q;
    cin >> n >> m >> q;
    for(i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        edges[i] = {x, y};
    }
    DFS(1, 0);
    for(int j = 1; j <= nr_of_bits; j++){
        for(i = 1; i <= n; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    for(int i = 1; i <= n; i++)
        changeval(i, 1);
    while(m--){
        int x;
        cin >> x;
        stare[x] ^= 1;
        if(stare[x] == 1){
            int a = edges[x].second;
            int b = edges[x].first;
            if(lvl[a] > lvl[b]){
                swap(a, b);
            }
            int sa = val(a);
            int sb = val(b);
            aib.update(timp[b].first, 1);
            aib.update(timp[b].second + 1, -1);
            changeval(a, sa + sb - last[x]);
        }else{
            int a = edges[x].second;
            int b = edges[x].first;
            if(lvl[a] > lvl[b]){
                swap(a, b);
            }
            last[x] = val(a);
            aib.update(timp[b].first, -1);
            aib.update(timp[b].second + 1, 1);
            ///un pas f important
            changeval(a, last[x]);
            changeval(b, last[x]);
        }
    }
    while(q--){
        int x;
        cin >> x;
        cout << val(x) << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2708 KB Output is correct
4 Correct 3 ms 2676 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 36 ms 4364 KB Output is correct
8 Correct 26 ms 4372 KB Output is correct
9 Correct 31 ms 4428 KB Output is correct
10 Correct 469 ms 20312 KB Output is correct
11 Correct 486 ms 20440 KB Output is correct
12 Correct 1312 ms 23420 KB Output is correct
13 Correct 194 ms 20200 KB Output is correct
14 Correct 303 ms 19304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 19480 KB Output is correct
2 Correct 261 ms 21276 KB Output is correct
3 Correct 372 ms 22508 KB Output is correct
4 Correct 363 ms 22600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2680 KB Output is correct
6 Correct 5 ms 2916 KB Output is correct
7 Correct 47 ms 4684 KB Output is correct
8 Correct 1258 ms 24264 KB Output is correct
9 Correct 1026 ms 24440 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1057 ms 21436 KB Output is correct
2 Correct 431 ms 23632 KB Output is correct
3 Correct 475 ms 23756 KB Output is correct
4 Correct 424 ms 23792 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2676 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 31 ms 4472 KB Output is correct
7 Correct 512 ms 21188 KB Output is correct
8 Correct 1063 ms 24264 KB Output is correct
9 Correct 206 ms 21304 KB Output is correct
10 Correct 309 ms 20560 KB Output is correct
11 Correct 311 ms 22672 KB Output is correct
12 Correct 303 ms 22664 KB Output is correct
13 Correct 420 ms 23748 KB Output is correct