oj.uz

답안 #685010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685010 2023-01-23T05:23:12 Z flappybird 동기화 (JOI13_synchronization) C++17
0 / 100
 8000 ms 46216 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 202020
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
pii edges[MAX];
vector<pii> toggle[MAX];
int laston[MAX];
vector<int> adj[MAX];
int ans[MAX];
int vis[MAX];
int num[MAX];
map<int, int> mp[MAX];
int findnxt(int v, int e) { return edges[e].first + edges[e].second - v; }
map<int, int> mpall;
int mpsum;
void bottomup(int x, int p = 0, int isrt = 0) {
	mp[x].clear();
	mp[x][0] = 1;
	int i;
	for (auto e : adj[x]) {
		int v = findnxt(x, e);
		if (vis[v] || v == p) continue;
		if (toggle[e].empty()) continue;
		bottomup(v, x);
		for (i = 0; i < toggle[e].size(); i++) {
			int s;
			if (i) s = toggle[e][i - 1].second;
			else s = -1;
			int nxt = toggle[e][i].first;
			while (1) {
				auto it = mp[v].lower_bound(s);
				if (it == mp[v].end()) break;
				if (it->first >= nxt) break;
				mp[v][nxt] += it->second;
				mp[v].erase(it);
			}
		}
		while (mp[v].size() && mp[v].rbegin()->first >= toggle[e].back().second) mp[v].erase(mp[v].rbegin()->first);
		if (!isrt) {
			if (mp[v].size() > mp[x].size()) swap(mp[v], mp[x]);
			for (auto& [a, b] : mp[v]) mp[x][a] += b;
		}
	}
}
void topdown(int x, int p) {
	ans[x] += mpsum;
	int i;
	for (auto e : adj[x]) {
		int v = findnxt(x, e);
		if (vis[v] || v == p) continue;
		if (toggle[e].empty()) continue;
		vector<pii> logv;
		for (i = 0; i < toggle[e].size(); i++) {
			int s;
			if (i) s = toggle[e][i - 1].second;
			else s = -1;
			int nxt = toggle[e][i].first;
			while (1) {
				auto it = mpall.lower_bound(s);
				if (it == mpall.end()) break;
				if (it->first >= nxt) break;
				logv.emplace_back(it->first, it->second);
				logv.emplace_back(nxt, -it->second);
				mpall[nxt] += it->second;
				mpall.erase(it);
			}
		}
		while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) {
			mpsum -= mpall.rbegin()->second;
			logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second);
			mpall.erase(mpall.rbegin()->first);
		}
		topdown(v, x);
		for (auto& [a, b] : logv) mpall[a] += b, mpsum += b;
	}
}
void make_num(int x, int p = 0) {
	num[x] = 1;
	for (auto e : adj[x]) {
		int v = findnxt(x, e);
		if (v == p || vis[v]) continue;
		make_num(v, x);
		num[x] += num[v];
	}
}
void make_tree(int x) {
	make_num(x);
	int c = x;
	int n = num[x];
	while (1) {
		int changed = 0;
		for (auto e : adj[c]) {
			int v = findnxt(c, e);
			if (!vis[v] && num[v] < num[c]) {
				if (num[v] > n / 2) {
					c = v;
					changed = 1;
					break;
				}
			}
		}
		if (!changed) break;
	}
	bottomup(c, 0, 1);
	mpall.clear();
	mpsum = 0;
	for (auto e : adj[c]) {
		int v = findnxt(c, e);
		if (vis[v]) continue;
		for (auto& [a, b] : mp[v]) if (b) mpall[a] += b, mpsum += b;
	}
	for (auto& [a, b] : mp[c]) if (b) mpall[a] += b, mpsum += b;
	ans[c] += mpsum;
	int i;
	for (auto e : adj[c]) {
		int v = findnxt(c, e);
		if (vis[v]) continue;
		if (toggle[e].empty()) continue;
		for (auto& [a, b] : mp[v]) if (b) mpall[a] -= b, mpsum -= b;
		vector<pii> logv;
		for (i = 0; i < toggle[e].size(); i++) {
			int s;
			if (i) s = toggle[e][i - 1].second;
			else s = -1;
			int nxt = toggle[e][i].first;
			while (1) {
				auto it = mpall.lower_bound(s);
				if (it == mpall.end()) break;
				if (it->first >= nxt) break;
				logv.emplace_back(it->first, it->second);
				logv.emplace_back(nxt, -it->second);
				mpall[nxt] += it->second;
				mpall.erase(it);
			}
		}
		while (mpall.size() && mpall.rbegin()->first >= toggle[e].back().second) {
			mpsum -= mpall.rbegin()->second;
			logv.emplace_back(mpall.rbegin()->first, mpall.rbegin()->second);
			mpall.erase(mpall.rbegin()->first);
		}
		topdown(v, c);
		for (auto& [a, b] : logv) mpall[a] += b, mpsum += b;
		for (auto& [a, b] : mp[v]) if (b) mpall[a] += b, mpsum += b;
	}
	vis[c] = 1;
	for (auto e : adj[c]) {
		int v = findnxt(c, e);
		if (!vis[v]) make_tree(v);
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	int i, a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		edges[i] = pii(a, b);
		adj[a].push_back(i);
		adj[b].push_back(i);
	}
	for (i = 1; i <= M; i++) {
		cin >> a;
		if (laston[a]) {
			toggle[a].emplace_back(laston[a], i);
			laston[a] = 0;
		}
		else laston[a] = i;
	}
	for (i = 1; i < N; i++) if (laston[i]) toggle[i].emplace_back(laston[i], M + 1);
	make_tree(1);
	vector<int> qs;
	while (Q--) {
		cin >> a;
		qs.push_back(a);
	}
	for (auto v : qs) cout << ans[v] << ln;
}

Compilation message

synchronization.cpp: In function 'void bottomup(int, int, int)':
synchronization.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void topdown(int, int)':
synchronization.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'void make_tree(int)':
synchronization.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |   for (i = 0; i < toggle[e].size(); i++) {
      |               ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19284 KB Output is correct
2 Correct 9 ms 19244 KB Output is correct
3 Correct 9 ms 19332 KB Output is correct
4 Correct 11 ms 19332 KB Output is correct
5 Correct 11 ms 19308 KB Output is correct
6 Correct 14 ms 19468 KB Output is correct
7 Correct 57 ms 20736 KB Output is correct
8 Correct 53 ms 20816 KB Output is correct
9 Correct 67 ms 20712 KB Output is correct
10 Correct 811 ms 34708 KB Output is correct
11 Correct 737 ms 34692 KB Output is correct
12 Correct 203 ms 37836 KB Output is correct
13 Execution timed out 8029 ms 41608 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8021 ms 46216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19284 KB Output is correct
2 Correct 10 ms 19276 KB Output is correct
3 Incorrect 10 ms 19244 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 235 ms 36632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 19284 KB Output is correct
2 Correct 11 ms 19284 KB Output is correct
3 Correct 10 ms 19284 KB Output is correct
4 Correct 12 ms 19268 KB Output is correct
5 Incorrect 19 ms 19496 KB Output isn't correct
6 Halted 0 ms 0 KB -