Submission #468116

#	Time	Username	Problem	Language	Result	Execution time	Memory
468116		ommivorous	Synchronization (JOI13_synchronization)	C++14	0 / 100	271 ms	38708 KiB

synchronization

/*
thisiscaau's code
trying my best for a better future
*/
#include <bits/stdc++.h>

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);

using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define endl '\n'
typedef pair<ll,ll> ii;
ll const mod = 1e9 + 7, MAXN = 2e5 + 5,oo = 3e18;

class fenwick {
private : vector<ll> ft;
public :
	fenwick (ll n){
		ft.assign(n + 5,0);
	}

	ll ls (ll x){
		return x & (-x);
	}

	ll rsq (ll pos){
		if (pos == 0) return 0;
		ll res = 0;
		for ( ; pos ; pos -= ls(pos)){
			res += ft[pos];
		}
		return res;
	}

	void inc (ll pos,ll val){
		for ( ; pos < ft.size() ; pos += ls(pos)){
			ft[pos] += val;
		}
	}
};

fenwick ft(MAXN);

// difference array 

ll tc,n,m,q,now = 1;
vector<ll> g[MAXN];
ll tin[MAXN],tout[MAXN],save[MAXN];
ll dep[MAXN];
ll sz[MAXN];
ll up[MAXN][20];
bool rem[MAXN];

vector<ii> edges;
void dfs (ll u,ll p = 0){
	tin[u] = now++;
	up[u][0] = p;
	sz[u] = 1;
	for (int i = 1 ; i < 20 ; i++){
		up[u][i] = up[up[u][i - 1]][i - 1];
	}

	for (ll v : g[u]){
		if (v == p) continue;
		dep[v] = dep[u] + 1;
		dfs(v,u);
	}
	tout[u] = now;
}

ll find_root (ll u){
	// find root of u
	for (int i = 19 ; i >= 0 ; i--){
		if (up[u][i]){
			ll path_to_anc = ft.rsq(tin[up[u][i]]);
			ll path_to_node = ft.rsq(tin[u]);
			ll dist = dep[u] - dep[up[u][i]];
			if (path_to_anc + dist == path_to_node){
				u = up[u][i];
			}
		}
	}
	return u;
}

void aurelion_sol(){
	// solution goes here
	cin >> n >> m >> q;
	for (int i = 1 ; i < n ; i++){
		ll u,v; cin >> u >> v;
		g[u].pb(v); g[v].pb(u);
		edges.pb(mp(u,v));
	}
	dfs(1);
	for (auto &cur : edges){
		if (up[cur.fi][0] == cur.se) {
			swap(cur.fi,cur.se);
		}
	} 

	for (int i = 1 ; i <= m ; i++){
		ll edge_id; cin >> edge_id;
		ii cur = edges[edge_id - 1];
		if (!rem[edge_id]){
			// add edge
			ll root = find_root(cur.fi);
			sz[cur.fi] += sz[cur.se] - save[edge_id];
			ft.inc(tin[cur.se],1);
			ft.inc(tout[cur.se],-1);
		}
		else {
			// remove edge
			save[edge_id] = sz[cur.se] = sz[find_root(cur.fi)];
			ft.inc(tin[cur.se],-1);
			ft.inc(tout[cur.se],1);
		}
		rem[edge_id] = !rem[edge_id];
	}

	for (int i = 1 ;  i <= q ; i++){
		ll node; cin >> node;
		cout << sz[find_root(node)] << endl;
	}
}

signed main() {
#ifdef thisiscaau
	fileopen("input", "output");
#endif
#ifndef thisiscaau
	// fileopen1("LAH");
#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	tc = 1;
	while (tc--) aurelion_sol();
}

Compilation message (stderr)

synchronization.cpp: In member function 'void fenwick::inc(long long int, long long int)':
synchronization.cpp:41:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for ( ; pos < ft.size() ; pos += ls(pos)){
      |           ~~~~^~~~~~~~~~~
synchronization.cpp: In function 'void aurelion_sol()':
synchronization.cpp:111:7: warning: unused variable 'root' [-Wunused-variable]
  111 |    ll root = find_root(cur.fi);
      |       ^~~~

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