oj.uz

Submission #973466

# Submission time Handle Problem Language Result Execution time Memory
973466 2024-05-02T04:18:04 Z beaboss Synchronization (JOI13_synchronization) C++14
100 / 100
 365 ms 25340 KB 
// Source: https://oj.uz/problem/view/JOI13_synchronization
//  

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int B = 20;

int bit[N];
void add(int ind, int val) {
	for (; ind < N; ind += (ind & -ind)) {
		bit[ind] += val;
	}
}
int query(int ind) {
	int res = 0;
	for (; ind > 0; ind -= (ind & -ind)) {
		res += bit[ind];
	}
	return res;
}


vi adj[N];
vector<pii> con;
int lift[N][B], tin[N], tout[N], last[N], info[N], d[N], active[N];
int timer = 1;
void dfs(int cur, int par = 0) {
	lift[cur][0]=par;
	d[cur]=d[par]+1;
	tin[cur]=timer++;
	for (auto val: adj[cur]) {
		if (val != par) dfs(val, cur);
	}
	tout[cur]=timer;
}

int get(int cur) {
	int path = query(tin[cur]);
	for (int i = B - 1; i >= 0; i--) {
		if (lift[cur][i] != 0 && query(tin[lift[cur][i]]) == path) cur=lift[cur][i];
	}
	return cur;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, q;
	cin >> n >> m >> q;
	con.pb({0, 0});
	FOR(i, 0, n-1) {

		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
		con.pb({a, b});
	}

	dfs(1);
	FOR(j, 1, B) FOR(i, 1, n + 1) lift[i][j] = lift[lift[i][j-1]][j-1];

	FOR(i, 1, n + 1) {
		// cout << i << endl;
		add(tin[i], 1);
		add(tout[i], -1);
		info[i]=1;
	}
	FOR(_, 0, m) {
		int sw;cin >> sw;

		int a = con[sw].first;
		int b = con[sw].second;
		if (d[a] < d[b]) swap(a, b);
		// cout << a << b << endl;
		if (active[sw]) {
			info[a] = info[get(b)];
			last[sw] = info[a];
			add(tin[a], 1);
			add(tout[a], -1);
		} else {
			info[get(b)] += info[a] - last[sw];
			add(tin[a], -1);
			add(tout[a], 1);
		}

		// cout << query(1) << query(2) << endl;
		// FOR(i, 1, n +1 ) cout << info[get(i)] << ' ';
		// cout << endl;
		active[sw] = !active[sw]; 

	}
	FOR(_, 0, q) {
		int node;
		cin >> node;
		cout << info[get(node)] << endl;
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 9 ms 7528 KB Output is correct
8 Correct 9 ms 7516 KB Output is correct
9 Correct 9 ms 7516 KB Output is correct
10 Correct 96 ms 19656 KB Output is correct
11 Correct 97 ms 19548 KB Output is correct
12 Correct 157 ms 24132 KB Output is correct
13 Correct 56 ms 19396 KB Output is correct
14 Correct 70 ms 18544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 21444 KB Output is correct
2 Correct 66 ms 21396 KB Output is correct
3 Correct 71 ms 23408 KB Output is correct
4 Correct 79 ms 23200 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 2 ms 6500 KB Output is correct
4 Correct 1 ms 6500 KB Output is correct
5 Correct 2 ms 6496 KB Output is correct
6 Correct 3 ms 6756 KB Output is correct
7 Correct 25 ms 7944 KB Output is correct
8 Correct 309 ms 25028 KB Output is correct
9 Correct 311 ms 25032 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 25032 KB Output is correct
2 Correct 227 ms 24304 KB Output is correct
3 Correct 225 ms 24320 KB Output is correct
4 Correct 236 ms 24356 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 22 ms 7516 KB Output is correct
7 Correct 241 ms 20424 KB Output is correct
8 Correct 365 ms 25340 KB Output is correct
9 Correct 177 ms 20676 KB Output is correct
10 Correct 202 ms 19960 KB Output is correct
11 Correct 196 ms 22760 KB Output is correct
12 Correct 189 ms 22928 KB Output is correct
13 Correct 229 ms 24360 KB Output is correct