oj.uz

Submission #751026

# Submission time Handle Problem Language Result Execution time Memory
751026 2023-05-30T20:11:02 Z jmyszka2007 Synchronization (JOI13_synchronization) C++17
0 / 100
 8000 ms 97328 KB 
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
constexpr int LIM = 2e5;
constexpr int base = (1 << 18);
pair<int, int>kr[LIM + 10];
vector<int>g[LIM + 10];
int kt[LIM + 10];
int val[LIM + 10];
int pop[LIM + 10];
int nxt[LIM + 10][19];
int siz[LIM + 10];
int pre[LIM + 10];
int dep[LIM + 10];
int tri[2 * base];
int aktpre = 1;
void dfs(int v, int o) {
	dep[v] = dep[o] + 1;
	pre[v] = aktpre++;
	nxt[v][0] = o;
	for(int i = 1; i <= 18; i++) {
		nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
	}
	siz[v] = 1;
	for(auto x : g[v]) {
		if(x != o) {
			dfs(x, v);
			siz[v] += siz[x];
		}
	}
}
void upd(int l, int r, int x) {
	l += base;
	r += base;
	while(l <= r) {
		if(l & 1) {
			tri[l] += x;
		}
		if(!(r & 1)) {
			tri[r] += x;
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
}
int que(int v) {
	v += base;
	int ans = 0;
	while(v > 0) {
		ans += tri[v];
		v /= 2;
	}
	return ans;
}
int find(int v) {
	for(int i = 18; i >= 0; i--) {
		if(que(pre[v]) - que(pre[nxt[v][i]]) == dep[v] - dep[nxt[v][i]]) {
			v = nxt[v][i];
		}
	}
	return v;
}
void uni(int a, int b) {
	if(pre[a] > pre[b]) {
		swap(a, b);
	}
	upd(pre[b], pre[b] + siz[b] - 1, 1); 
}
void disuni(int a, int b) {
	if(pre[a] > pre[b]) {
		swap(a, b);
	}
	upd(pre[b], pre[b] + siz[b] - 1, -1); 
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i++) {
		val[i] = 1;
	}
	for(int i = 1; i < n; i++) {
		cin >> kr[i].st >> kr[i].nd;
		g[kr[i].st].push_back(kr[i].nd);
		g[kr[i].nd].push_back(kr[i].st);
	}
	dfs(1, 1);
	for(int i = 1; i <= m; i++) {
		int x;
		cin >> x;
		kt[x]++;
		if(kt[x] & 1) {
			cout << kr[x].st << ' ' << kr[x].nd << '\n';
			int tmp = val[find(kr[x].st)] + val[find(kr[x].nd)] - pop[x];
			uni(kr[x].st, kr[x].nd);
			val[find(kr[x].st)] = tmp;
		}
		else {
			cout << kr[x].st << ' ' << kr[x].nd << '\n';
			pop[x] = val[find(kr[x].st)];
			disuni(kr[x].st, kr[x].nd);
			val[find(kr[x].st)] = pop[x];
			val[find(kr[x].nd)] = pop[x];
		}
		for(int j = 1; j <= n; j++) {
			cout << find(j) << ' ';
		}
		cout << '\n';
	}
	while(q--) {
		int x;
		cin >> x;
		cout << val[find(x)] << '\n';
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8026 ms 90768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8026 ms 97328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5036 KB Output isn't correct
2 Halted 0 ms 0 KB -