Submission #1292350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292350		Minbaev	Synchronization (JOI13_synchronization)	C++20	0 / 100	277 ms	41296 KiB

synchronization

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimize("Ofast,unroll-loops")
//~ #pragma GCC optimize("Ofast,no-stack-protector")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")


using namespace std;
using namespace __gnu_pbds;

#define pb      push_back
#define all(x)  x.begin(),x.end()
#define int     long long
// #define double  long double
#define ar      array
#define mrand(a, b)   uniform_int_distribution<int>(a, b)(rng)

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

template<class T> using ste = tree<T, null_type, less_equal<T>,
rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int binpow(int a, int b, int m){
    if(b <= 0)return 1; 	
    if(b % 2 == 0){
        int c = binpow(a,b/2,m);
        return (c*c)%m;
    }
    return (binpow(a,b-1,m)*a)%m;
}

int divi(int a, int b, int m){
    return (a*(binpow(b,m-2, m)))%m;
}

namespace FAST {
    template<typename T>
    istream &operator>>(istream &cin, vector<T> &a) {
    for (T &i: a) cin >> i;
        return cin;
    }

    template<typename T>
    ostream &operator<<(ostream &cout, vector<T> &a) {
          for (T i: a) cout << i << ' ';
        return cout;
    }
}
using namespace FAST;

const int inf = 3e18 + 7;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int md = 998244353;

int rev(int a, int m){
	if (a == 1)return 1;
	return (1 - rev(m % a, a) * m) / a + m;
}

struct Bit {
    vector<int> b, b2;
    int n;

    Bit(int n) {
        this->n = n + 1;
        b.assign(n + 1, 0);
        b2.assign(n+1, 0);
    }

    void add(vector<int>&b, int idx, int x){
        while(idx <= n){
            b[idx] += x;
            idx += idx & -idx;
        }
    }

    void upd(int l, int r, int x){
        add(b, l, x);
        add(b, r+1, -x);
        add(b2, l, x*(l-1));
        add(b2, r+1, -x*r);
    }

    int sum(vector<int>&b, int idx){
        int res = 0;
        while(idx > 0){
            res += b[idx];
            idx -= idx & -idx;
        }
        return res;
    }

    int pref(int idx){
        return sum(b, idx) * idx - sum(b2, idx);
    }

    int get(int l, int r){                  
        return pref(r) - pref(l-1);
    }
};

int n,m,k;
vector<ar<int,2>>g[N], vs;
vector<int>sz(N), head(N), id(N), dep(N), id_(N), p(N);
int timer;
Bit t(N * 4);

void dfs(int x, int pr){
	sz[x] = 1; p[x] = pr;
	
	for(auto &[to, ind] : g[x]){
		if(to == pr)continue;
		dep[to] = dep[x] + 1;
		dfs(to, x);
		sz[x] += sz[to];
		if(vs[ind][0] == to)swap(vs[ind][0], vs[ind][1]);
	}
}

void hld(int x, int pr){
	int hv = 0;
	timer += 1; id[x] = timer; id_[timer] = x;
	
	for(auto &[to, ind] : g[x]){
		if(to == pr)continue;
		if(hv == 0 || sz[hv] < sz[to])hv = to;
	}
	
	if(hv){
		head[hv] = head[x];
		hld(hv, x);
	}
	
	for(auto &[to, ind] : g[x]){
		if(to == hv || to == pr)continue;
		head[to] = to;
		hld(to, x);
	}
}

int up(int x){
	int h = head[x];
	if(t.get(id[h], id[x]) == dep[x] - dep[h] + 1){
		if(p[h] == h)return h;
		return up(p[h]);
	}
	
	for(int i = 19;i>=0;i--){
		int num = id[x] - (1ll << i);
		if(num < id[h])continue;
		int l = num += 1;
		int node = id_[num];
		if(t.get(l, id[x]) == dep[x] - dep[node]){
			x = node;
		}
	}
	
	return x;
}

void solve(){
	
	cin >> n >> m >> k;
	
	vs.pb({1, 1});
	
	for(int i = 2;i<=n;i++){
		int a,b;
		cin >> a >> b;
		vs.pb({a, b});
		g[a].pb({b, i-1});
		g[b].pb({a, i-1});
	}
	
	head[1] = 1;
	dfs(1, 1);
	hld(1, 1);
	
	vector<int>res(n + 1, 1), last(n + 1), cnt(n + 1);
	
	for(int i = 1;i<=m;i++){
		int a;
		cin >> a;
		int u = vs[a][0], v = vs[a][1];
		if(cnt[a] == 0){
			int b = up(u);
			res[b] += res[v] - last[a];
			t.upd(id[v], id[v], 1);
		}
		else{
			int b = up(u);
			res[v] = res[b];
			last[a] = res[b];
			t.upd(id[v], id[v], -1);
		}
		cnt[a] ^= 1;
	}
	
	for(int i = 1;i<=k;i++){
		int a;
		cin >> a;
		cout << res[up(a)] << "\n";
	}
	
	
}
/*
9 10 9 
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

2 
3 
5 
6 
4 
4 
1 
7 
8 
4 

1
2
3
4
5
6
7
8
9
*/
 signed main()
{
//  freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int tt=1;//cin >> tt;
    while(tt--)solve();	

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 40