제출 #440967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440967		Vladth11	동기화 (JOI13_synchronization)	C++14	100 / 100	1312 ms	24440 KiB

synchronization

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40