oj.uz

Submission #116227

# Submission time Handle Problem Language Result Execution time Memory
116227 2019-06-11T11:00:27 Z Just_Solve_The_Problem Synchronization (JOI13_synchronization) C++11
100 / 100
 326 ms 21236 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)2e5 + 7;

vector<int> gr[N];
vector<pair<int, int>> ed;

int n, m, q;
int tin[N], tout[N], pos[N];
int st[N];
int tiktak;
int tree[N * 4], ans[N], lst[N];

void dfs(int v, int pr) {
	tin[v] = ++tiktak;
	pos[tiktak] = v;
	for (int id : gr[v]) {
		int to = ed[id].first + ed[id].second - v;
		if (to == pr) continue;
		dfs(to, v);
	}
	tout[v] = ++tiktak;
}

void build(int v, int l, int r) {
	if (l == r) {
		tree[v] = tout[pos[l]];
		return ;
	}
	int mid = (l + r) >> 1;
	build(v + v, l, mid);
	build(v + v + 1, mid + 1, r);
	tree[v] = max(tree[v + v], tree[v + v + 1]);
}

void upd(int pos, int val, int v = 1, int tl = 1, int tr = n + n) {
	if (tl == tr) {
		tree[v] = val;
		return ;
	}
	int mid = (tl + tr) >> 1;
	if (pos <= mid) {
		upd(pos, val, v + v, tl, mid);
	} else {
		upd(pos, val, v + v + 1, mid + 1, tr);
	}
	tree[v] = max(tree[v + v], tree[v + v + 1]);
}

int find(int l, int r, int lim, int v = 1, int tl = 1, int tr = n + n) {
	if (tl > r || tr < l || tree[v] <= lim) return -1;
	if (tl == tr) return tl;
	int mid = (tl + tr) >> 1;
	int res = find(l, r, lim, v + v + 1, mid + 1, tr);
	if (res == -1) res = find(l, r, lim, v + v, tl, mid);
	return res;
}

int get(int l, int r, int v = 1, int tl = 1, int tr = n + n) {
	if (tl > r || tr < l) return -1;
	if (l <= tl && tr <= r) return tree[v];
	int mid = (tl + tr) >> 1;
	return max(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}

int findroot(int u) {
	int res = find(1, tin[u], tin[u]);
	return (res == -1) ? 1 : pos[res];
}

main() {
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		gr[u].push_back(ed.size());
		gr[v].push_back(ed.size());
		ed.push_back({u, v});
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) {
		ans[i] = 1;
	}
	for (int i = 0; i < n - 1; i++) {
		if (tin[ed[i].first] > tin[ed[i].second]) 
			swap(ed[i].first, ed[i].second);
	}
	build(1, 1, n + n);
	for (int i = 1; i <= m; i++) {
		int id;
		scanf("%d", &id); id--;
		int u = findroot(ed[id].first);
		int v = ed[id].second;
		if (!st[id]) {
			ans[u] += ans[v] - lst[v];
			upd(tin[v], tin[v]);
		} else {
			ans[v] = lst[v] = ans[u];
			upd(tin[v], tout[v]);
		}
		st[id] ^= 1;
		//cout << find(1, tin[ed[id].first], tin[ed[id].first]) << ' ' << ed[id].first << ' ' << u << endl;
		//cout << "ZASDSDA " << get(2, 2) << endl;
	}
	for (int i = 1; i <= n; i++) {
		ans[i] = ans[findroot(i)];
	}
	for (int i = 1, x; i <= q; i++) {
		scanf("%d", &x);
		printf("%d\n", ans[x]);
	}
}

Compilation message

synchronization.cpp:73:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &id); id--;
   ~~~~~^~~~~~~~~~~
synchronization.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 24 ms 6144 KB Output is correct
8 Correct 22 ms 6272 KB Output is correct
9 Correct 22 ms 6272 KB Output is correct
10 Correct 302 ms 16296 KB Output is correct
11 Correct 326 ms 16236 KB Output is correct
12 Correct 242 ms 20388 KB Output is correct
13 Correct 210 ms 16096 KB Output is correct
14 Correct 234 ms 15336 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 17856 KB Output is correct
2 Correct 128 ms 17720 KB Output is correct
3 Correct 110 ms 19468 KB Output is correct
4 Correct 107 ms 19436 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 23 ms 5248 KB Output is correct
7 Correct 22 ms 6784 KB Output is correct
8 Correct 256 ms 21208 KB Output is correct
9 Correct 231 ms 21220 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 21232 KB Output is correct
2 Correct 129 ms 20616 KB Output is correct
3 Correct 133 ms 20668 KB Output is correct
4 Correct 160 ms 20716 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 7 ms 5140 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 23 ms 6272 KB Output is correct
7 Correct 301 ms 17120 KB Output is correct
8 Correct 255 ms 21236 KB Output is correct
9 Correct 201 ms 17252 KB Output is correct
10 Correct 222 ms 16532 KB Output is correct
11 Correct 151 ms 19080 KB Output is correct
12 Correct 151 ms 19048 KB Output is correct
13 Correct 127 ms 20604 KB Output is correct