Submission #35781

#	Time	Username	Problem	Language	Result	Execution time	Memory
35781		UncleGrandpa925	Synchronization (JOI13_synchronization)	C++14	100 / 100	933 ms	18724 KiB

synchronization

/*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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40