oj.uz

Submission #35781

# Submission time Handle Problem Language Result Execution time Memory
35781 2017-11-29T14:42:23 Z UncleGrandpa925 Synchronization (JOI13_synchronization) C++14
100 / 100
 933 ms 18724 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 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() {
	scanf("%d %d %d", &n, &m, &q);
	edge.push_back(mp(-1, -1));
	for (int i = 1; i <= n - 1; i++) {
		int u, v; scanf("%d %d", &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; printf("%d\n", ans[u]);
	}
}

Compilation message

synchronization.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<int>&)':
synchronization.cpp:21: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<int, int> >&)':
synchronization.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
synchronization.cpp: In function 'int main()':
synchronization.cpp:98:31: 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:101:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
                                   ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9928 KB Output is correct
2 Correct 0 ms 9928 KB Output is correct
3 Correct 0 ms 9928 KB Output is correct
4 Correct 0 ms 9928 KB Output is correct
5 Correct 0 ms 9928 KB Output is correct
6 Correct 3 ms 9928 KB Output is correct
7 Correct 33 ms 10456 KB Output is correct
8 Correct 26 ms 10456 KB Output is correct
9 Correct 23 ms 10456 KB Output is correct
10 Correct 419 ms 14148 KB Output is correct
11 Correct 469 ms 14144 KB Output is correct
12 Correct 409 ms 18720 KB Output is correct
13 Correct 279 ms 14640 KB Output is correct
14 Correct 266 ms 14148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 16560 KB Output is correct
2 Correct 216 ms 16500 KB Output is correct
3 Correct 149 ms 18720 KB Output is correct
4 Correct 156 ms 18720 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9928 KB Output is correct
2 Correct 0 ms 9928 KB Output is correct
3 Correct 3 ms 9928 KB Output is correct
4 Correct 3 ms 9928 KB Output is correct
5 Correct 0 ms 9928 KB Output is correct
6 Correct 3 ms 9928 KB Output is correct
7 Correct 33 ms 10704 KB Output is correct
8 Correct 713 ms 18724 KB Output is correct
9 Correct 813 ms 18720 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 18724 KB Output is correct
2 Correct 579 ms 18560 KB Output is correct
3 Correct 496 ms 18724 KB Output is correct
4 Correct 396 ms 18720 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9928 KB Output is correct
2 Correct 0 ms 9928 KB Output is correct
3 Correct 0 ms 9928 KB Output is correct
4 Correct 0 ms 9928 KB Output is correct
5 Correct 6 ms 9928 KB Output is correct
6 Correct 53 ms 10456 KB Output is correct
7 Correct 933 ms 14144 KB Output is correct
8 Correct 763 ms 18720 KB Output is correct
9 Correct 709 ms 14640 KB Output is correct
10 Correct 633 ms 14148 KB Output is correct
11 Correct 546 ms 16560 KB Output is correct
12 Correct 513 ms 16560 KB Output is correct
13 Correct 523 ms 18724 KB Output is correct