oj.uz

Submission #35780

# Submission time Handle Problem Language Result Execution time Memory
35780 2017-11-29T14:41:20 Z UncleGrandpa925 Synchronization (JOI13_synchronization) C++14
30 / 100
 373 ms 25276 KB 
/*input
5 6 3
1 2
1 3
2 4
2 5
1 2 1 4 4
3 1 4 5
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 100005
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n, m, q;
vector<vector<int> > a(N);
vector<pair<int, int> > edge;
bool state[N];
int sta[N], en[N];
int pos[2 * N];
int Time = 0;
int f[8 * N];
int last[N];
int ans[N];

void dfs(int u, int p) {
	sta[u] = ++Time;
	pos[Time] = u;
	for (auto v : a[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	en[u] = ++Time;
}

void init(int k, int l, int r) {
	if (l == r) {
		f[k] = en[pos[l]];
		return;
	}
	int mid = (l + r) / 2;
	init(k * 2, l, mid); init(k * 2 + 1, mid + 1, r);
	f[k] = max(f[k * 2], f[k * 2 + 1]);
}

void update(int k, int l, int r, int pos, int val) {
	if (r < pos || pos < l) return;
	if (l == r && pos == l) {
		f[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	update(k * 2, l, mid, pos, val); update(k * 2 + 1, mid + 1, r, pos, val);
	f[k] = max(f[k * 2], f[k * 2 + 1]);
}

int find(int k, int l, int r, int L, int R, int base) {
	if (r < L || R < l || f[k] <= base) return -1;
	if (l == r) return l;
	int mid = (l + r) / 2;
	int rec = find(k * 2 + 1, mid + 1, r, L, R, base);
	if (rec == -1) rec = find(k * 2, l, mid, L, R, base);
	return rec;
}

int get(int k, int l, int r, int L, int R) {
	if (r < L || R < l) return -1;
	if (L <= l && r <= R) return f[k];
	int mid = (l + r) / 2;
	return max(get(k * 2, l, mid, L, R), get(k * 2 + 1, mid + 1, r, L, R));
}

int findroot(int u) {
	int rec = find(1, 1, 2 * n, 1, sta[u], sta[u]);
	if (rec == -1) return 1;
	return pos[rec];
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	edge.push_back(mp(-1, -1));
	for (int i = 1; i <= n - 1; i++) {
		int u, v; cin >> u >> v;
		edge.push_back(mp(u, v));
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) {
		ans[i] = 1;
		if (sta[edge[i].fi] > sta[edge[i].se]) swap(edge[i].fi, edge[i].se);
	}
	init(1, 1, 2 * n);
	for (int i = 1; i <= m; i++) {
		int e; cin >> e;
		int u = edge[e].fi; int v = edge[e].se;
		u = findroot(u);
		if (!state[e]) {
			ans[u] = ans[u] + ans[v] - last[v];
			update(1, 1, 2 * n, sta[v], sta[v]);
		}
		else {
			last[v] = ans[v] = ans[u];
			update(1, 1, 2 * n, sta[v], en[v]);
		}
		state[e] ^= 1;
	}
	for (int i = 1; i <= n; i++) ans[i] = ans[findroot(i)];
	for (int i = 1; i <= q; i++) {
		int u; cin >> u; cout << ans[u] << endl;
	}
}

Compilation message

synchronization.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
synchronization.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
synchronization.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
synchronization.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15560 KB Output is correct
2 Correct 0 ms 15560 KB Output is correct
3 Correct 0 ms 15560 KB Output is correct
4 Correct 0 ms 15560 KB Output is correct
5 Correct 0 ms 15560 KB Output is correct
6 Correct 3 ms 15560 KB Output is correct
7 Correct 16 ms 16224 KB Output is correct
8 Correct 23 ms 16224 KB Output is correct
9 Correct 16 ms 16224 KB Output is correct
10 Correct 373 ms 21320 KB Output is correct
11 Correct 363 ms 21320 KB Output is correct
12 Correct 273 ms 25272 KB Output is correct
13 Correct 263 ms 21756 KB Output is correct
14 Correct 239 ms 21320 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 23488 KB Output is correct
2 Correct 156 ms 23436 KB Output is correct
3 Correct 116 ms 25272 KB Output is correct
4 Correct 149 ms 25268 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15560 KB Output is correct
2 Correct 0 ms 15560 KB Output is correct
3 Correct 0 ms 15560 KB Output is correct
4 Correct 0 ms 15560 KB Output is correct
5 Correct 0 ms 15560 KB Output is correct
6 Correct 3 ms 15560 KB Output is correct
7 Runtime error 13 ms 16488 KB Execution killed because of forbidden syscall writev (20)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 273 ms 25276 KB Execution killed because of forbidden syscall writev (20)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15560 KB Output is correct
2 Correct 0 ms 15560 KB Output is correct
3 Correct 0 ms 15560 KB Output is correct
4 Correct 0 ms 15560 KB Output is correct
5 Correct 0 ms 15560 KB Output is correct
6 Runtime error 23 ms 16224 KB Execution killed because of forbidden syscall writev (20)
7 Halted 0 ms 0 KB -