oj.uz

Submission #468117

# Submission time Handle Problem Language Result Execution time Memory
468117 2021-08-26T16:11:01 Z ommivorous Synchronization (JOI13_synchronization) C++14
100 / 100
 408 ms 38836 KB 
/*
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[root] += 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

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)){
      |           ~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 4 ms 6604 KB Output is correct
4 Correct 4 ms 6604 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 6 ms 6860 KB Output is correct
7 Correct 19 ms 9220 KB Output is correct
8 Correct 18 ms 9416 KB Output is correct
9 Correct 18 ms 9288 KB Output is correct
10 Correct 245 ms 33876 KB Output is correct
11 Correct 250 ms 33904 KB Output is correct
12 Correct 321 ms 37952 KB Output is correct
13 Correct 106 ms 33580 KB Output is correct
14 Correct 164 ms 32488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 32992 KB Output is correct
2 Correct 109 ms 34688 KB Output is correct
3 Correct 139 ms 36660 KB Output is correct
4 Correct 140 ms 36628 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6520 KB Output is correct
3 Correct 4 ms 6604 KB Output is correct
4 Correct 4 ms 6604 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 5 ms 6860 KB Output is correct
7 Correct 25 ms 9784 KB Output is correct
8 Correct 397 ms 38728 KB Output is correct
9 Correct 406 ms 38736 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 35804 KB Output is correct
2 Correct 231 ms 37740 KB Output is correct
3 Correct 220 ms 37864 KB Output is correct
4 Correct 224 ms 37820 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 4 ms 6600 KB Output is correct
4 Correct 4 ms 6596 KB Output is correct
5 Correct 5 ms 6868 KB Output is correct
6 Correct 23 ms 9372 KB Output is correct
7 Correct 330 ms 34656 KB Output is correct
8 Correct 408 ms 38836 KB Output is correct
9 Correct 156 ms 34732 KB Output is correct
10 Correct 222 ms 33708 KB Output is correct
11 Correct 145 ms 36276 KB Output is correct
12 Correct 141 ms 36168 KB Output is correct
13 Correct 213 ms 37812 KB Output is correct