oj.uz

Submission #552214

# Submission time Handle Problem Language Result Execution time Memory
552214 2022-04-22T19:01:51 Z Arnch Synchronization (JOI13_synchronization) C++17
100 / 100
 3497 ms 81440 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
#pragma GCC optimzie("Ofast")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endlefii
#define endl '\n'

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, Log = 30;

struct node {
	int cnt, lz;
	node() {
		cnt = lz = 0;
	}
} x[N << 2];
int u[N], v[N], h[N], st[N], fn[N], par[N][Log], tim, n, m, q;
ll last[N], sum[N];
bool vis[N];
vector<int> vc, G[N];

void dfs(int x, int p = 0) {
	par[x][0] = p;
	for(int i = 1; i < Log; i++) par[x][i] = par[par[x][i - 1]][i - 1];

	h[x] = h[p] + 1;
	st[x] = tim++;
	for(auto &i : G[x]) {
		if(i == p) continue;
		dfs(i, x);
	}
	fn[x] = tim;
}

void put(int l, int r, int v) {
	if(x[v].lz == 0) return;
	x[2 * v].cnt += x[v].lz, x[2 * v].lz += x[v].lz;
	x[2 * v + 1].cnt += x[v].lz, x[2 * v + 1].lz += x[v].lz;
	x[v].lz = 0;
}

void change(int l, int r, int s, int e, int val, int v) {
	if(r <= s || l >= e) return;
	if(l >= s && r <= e) {
		x[v].cnt += val;
		x[v].lz += val;
		return;
	}
	put(l, r, v);
	int mid = (l + r) >> 1;
	change(l, mid, s, e, val, 2 * v), change(mid, r, s, e, val, 2 * v + 1);
}

int get(int l, int r, int ind, int v) {
	if(r - l < 2) return x[v].cnt;
	put(l, r, v);
	int mid = (l + r) >> 1;
	if(ind < mid) return get(l, mid, ind, 2 * v);
	return get(mid, r, ind, 2 * v + 1);
}

int get_par(int x) {
	for(int i = Log - 1; i >= 0; i--) {
		int val = get(0, n, st[par[x][i]], 1);
		int val2 = get(0, n, st[x], 1);
		if(val2 == val + (h[x] - h[par[x][i]])) x = par[x][i];
	}
	return x;
}


int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	cin >>n >>m >>q;
	for(int i = 1; i <= n - 1; i++) {
		cin >>u[i] >>v[i];
		G[u[i]].push_back(v[i]), G[v[i]].push_back(u[i]);
	}

	dfs(1);	

	for(int i = 1; i <= n - 1; i++) {
		if(h[u[i]] > h[v[i]]) swap(u[i], v[i]);
	}

	for(int i = 1; i <= n; i++) sum[i] = 1;

	while(m--) {
		int ind; cin >>ind;
		int ui = u[ind], vi = v[ind];
		int pu = get_par(ui), pv = get_par(vi);
		if(!vis[ind]) {
			vis[ind] = 1;
			int bac = sum[pu] + sum[pv] - last[ind];
			change(0, n, st[vi], fn[vi], 1, 1);
			pu = get_par(ui);
			sum[pu] = bac;
		}
		else {
			vis[ind] = 0;
			last[ind] = sum[pu];
			change(0, n, st[vi], fn[vi], -1, 1);
			pu = get_par(ui), pv = get_par(vi);
			sum[pu] = last[ind], sum[pv] = last[ind];
		}
	}

	while(q--) {
		int ind; cin >>ind;
		int p = get_par(ind);
		cout<<sum[p] <<endl;
	}

    return 0;
}

Compilation message

synchronization.cpp:11: warning: ignoring '#pragma GCC optimzie' [-Wunknown-pragmas]
   11 | #pragma GCC optimzie("Ofast")
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 55124 KB Output is correct
2 Correct 26 ms 55132 KB Output is correct
3 Correct 25 ms 55124 KB Output is correct
4 Correct 31 ms 55124 KB Output is correct
5 Correct 29 ms 55084 KB Output is correct
6 Correct 42 ms 55260 KB Output is correct
7 Correct 230 ms 57220 KB Output is correct
8 Correct 235 ms 57228 KB Output is correct
9 Correct 242 ms 57224 KB Output is correct
10 Correct 2712 ms 76064 KB Output is correct
11 Correct 2672 ms 76068 KB Output is correct
12 Correct 3370 ms 80648 KB Output is correct
13 Correct 2224 ms 75980 KB Output is correct
14 Correct 1206 ms 74716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2251 ms 75628 KB Output is correct
2 Correct 2246 ms 77244 KB Output is correct
3 Correct 1338 ms 79324 KB Output is correct
4 Correct 1354 ms 79308 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55124 KB Output is correct
2 Correct 32 ms 55060 KB Output is correct
3 Correct 29 ms 55124 KB Output is correct
4 Correct 29 ms 55176 KB Output is correct
5 Correct 28 ms 55144 KB Output is correct
6 Correct 43 ms 55348 KB Output is correct
7 Correct 285 ms 57428 KB Output is correct
8 Correct 3451 ms 78476 KB Output is correct
9 Correct 3475 ms 78556 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3497 ms 78516 KB Output is correct
2 Correct 1717 ms 77984 KB Output is correct
3 Correct 1752 ms 78236 KB Output is correct
4 Correct 1759 ms 78192 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 55124 KB Output is correct
2 Correct 25 ms 55152 KB Output is correct
3 Correct 31 ms 55100 KB Output is correct
4 Correct 27 ms 55120 KB Output is correct
5 Correct 44 ms 55400 KB Output is correct
6 Correct 258 ms 57268 KB Output is correct
7 Correct 2879 ms 76824 KB Output is correct
8 Correct 3420 ms 81440 KB Output is correct
9 Correct 2433 ms 77220 KB Output is correct
10 Correct 1533 ms 75924 KB Output is correct
11 Correct 2527 ms 79036 KB Output is correct
12 Correct 2542 ms 78656 KB Output is correct
13 Correct 1733 ms 80608 KB Output is correct