oj.uz

Submission #540403

# Submission time Handle Problem Language Result Execution time Memory
540403 2022-03-20T09:59:34 Z Vladth11 Synchronization (JOI13_synchronization) C++14
100 / 100
 914 ms 24476 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 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 1 ms 2620 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 23 ms 4440 KB Output is correct
8 Correct 21 ms 4504 KB Output is correct
9 Correct 20 ms 4368 KB Output is correct
10 Correct 368 ms 20432 KB Output is correct
11 Correct 356 ms 20536 KB Output is correct
12 Correct 770 ms 23608 KB Output is correct
13 Correct 149 ms 20224 KB Output is correct
14 Correct 243 ms 19364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 21484 KB Output is correct
2 Correct 223 ms 21420 KB Output is correct
3 Correct 283 ms 22600 KB Output is correct
4 Correct 276 ms 22552 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 2688 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 5 ms 2828 KB Output is correct
7 Correct 38 ms 4800 KB Output is correct
8 Correct 872 ms 24476 KB Output is correct
9 Correct 820 ms 24268 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 914 ms 24404 KB Output is correct
2 Correct 345 ms 23672 KB Output is correct
3 Correct 348 ms 23780 KB Output is correct
4 Correct 341 ms 23700 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 2772 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 4 ms 2772 KB Output is correct
6 Correct 25 ms 4484 KB Output is correct
7 Correct 411 ms 21096 KB Output is correct
8 Correct 814 ms 24284 KB Output is correct
9 Correct 179 ms 21388 KB Output is correct
10 Correct 236 ms 20560 KB Output is correct
11 Correct 260 ms 22604 KB Output is correct
12 Correct 252 ms 22632 KB Output is correct
13 Correct 423 ms 23752 KB Output is correct