oj.uz

Submission #415110

# Submission time Handle Problem Language Result Execution time Memory
415110 2021-05-31T14:36:47 Z Kevin_Zhang_TW Simurgh (IOI17_simurgh) C++17
100 / 100
 480 ms 6628 KB 
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// My bug list :
// integer overflow
// 0based, 1based forgotten
// index out of bound
// n, m, i, j typo
// some cases are missing

int mqcnt;

int qry(vector<int> r) { ++mqcnt; return count_common_roads(r); }

const int MAX_N = 505;

int id[MAX_N][MAX_N], state[MAX_N][MAX_N];

int dep[MAX_N], pa[MAX_N], n;

bool vis[MAX_N], on_tree[MAX_N][MAX_N];

vector<pair<int,int>> te, alle;
vector<int> tid;

void dfs(int x, int lst) {
	pa[x] = lst;
	dep[x] = dep[lst] + 1;

	vis[x] = true;
	for (int i = 0;i < n;++i) if (!vis[i] && id[x][i] != -1) {
		dfs(i, x);
		te.pb(i, x);
		tid.pb(id[i][x]);
		on_tree[i][x] = on_tree[x][i] = true;
	}
}
pair<vector<int>, vector<int>> get_path(int a, int b) {
	vector<int> l, r;
	while (a != b) {
		if (dep[a] > dep[b]) {
			l.pb(a);
			a = pa[a];
		}
		else {
			r.pb(b);
			b = pa[b];
		}
	}
	return {l, r};
}
vector<int> operator - (vector<int> a, int v) { assert(count(AI(a), v)); a.erase(find(AI(a), v)); return a; }
vector<int> operator + (vector<int> a, int v) { a.pb(v); return a; }

struct dsu {
	vector<int> g, sz;
	int F(int i) { return i == g[i] ? i : g[i] = F(g[i]); }
	bool M(int a, int b) { 
		a = F(a), b = F(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		return g[b] = a, sz[a] += sz[b], true;
	}
	dsu(int n) { g.resize(n+10), sz.resize(n+10, 1); iota(AI(g), 0); }
};

int get_cnt(vector<int> part) {
	vector<int> r = part;
	dsu D(n);
	for (int id : part) {
		auto [a, b] = alle[id];
		D.M(a, b);
	}
	int sum = 0;
	for (auto [a, b] : te)
		if (D.M(a, b)) {
			r.pb(id[a][b]);
			sum += state[a][b];
		}
	assert(r.size() == n-1);
	return qry(r) - sum;
}

void bs(vector<int> part, int sum) {
	if (sum == 0) return;
	if (part.size() == 1) {
		auto [a, b] = alle[ part[0] ];
		state[a][b] = state[b][a] = 1;
		return;
	}
	int mid = part.size()/2;
	vector<int> l, r;
	for (int i = 0;i < part.size();++i)
		(i<mid?l:r).pb(part[i]);

	int cl = get_cnt(l);
	bs(l, cl);
	bs(r, sum-cl);
}

void solve(int h) {
	vector<int> cur;
	for (int i = 0;i < n;++i) if (id[h][i] != -1 && state[i][h] == -1)
		cur.pb(id[h][i]);
	if (cur.empty()) return;
	bs(cur, get_cnt(cur));
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	int m = u.size();
	::n = n;
	for (int i = 0;i < n;++i) fill(id[i], id[i] + n, -1);
	for (int i = 0;i < m;++i) {
		int a = u[i], b = v[i];
		alle.pb(a, b);
		id[a][b] = id[b][a] = i;
		state[a][b] = state[b][a] = -1;
	}

	dfs(0, 0);

	int tsum = qry(tid);

	for (int i = 0;i < m;++i) {
		auto [a, b] = alle[i];
		if (on_tree[a][b]) continue;
		auto [l, r] = get_path(a, b);
		int cnt = 0;
		vector<int> not_sure, sure;
		for (int u : l)
			if (state[u][ pa[u] ] == -1)
				not_sure.pb(id[u][pa[u]]);
			else sure.pb(id[u][pa[u]]);
		for (int u : r)
			if (state[u][ pa[u] ] == -1)
				not_sure.pb(id[u][pa[u]]);
			else sure.pb(id[u][pa[u]]);

		if (not_sure.empty()) continue;

		vector<int> small, same, big;

		for (int eid : not_sure) {
			int qv = qry( (tid - eid) + id[a][b] );
			if (qv > tsum) big.pb(eid);
			if (qv == tsum) same.pb(eid);
			if (qv < tsum) small.pb(eid);
		}

		int cur_v = -1;
		if (small.size()) cur_v = 0;
		if (big.size()) cur_v = 1;
		if (cur_v == -1 && same.size() == l.size() + r.size())
			cur_v = 0;

		if (cur_v == -1 && sure.size()) {
			int qv = qry( (tid - sure[0]) + id[a][b] );
			auto [x, y] = alle[ sure[0] ];
			if (qv > tsum) cur_v = 1;
			if (qv == tsum) cur_v = state[x][y];
			if (qv < tsum) cur_v = 0;
		}

		for (int eid : big) {
			auto [x, y] = alle[eid];
			state[x][y] = state[y][x] = cur_v - 1;
		}

		for (int eid : small) {
			auto [x, y] = alle[eid];
			state[x][y] = state[y][x] = cur_v + 1;
		}

		for (int eid : same) {
			auto [x, y] = alle[eid];
			state[y][x] = state[x][y] = cur_v;
		}

		state[b][a] = state[a][b] = cur_v;
	}

	for (auto [a, b] : te) {
		if (state[a][b] == -1)
			state[a][b] = state[b][a] = 1;
	}

	assert(mqcnt <= n + n);

	for (int i = 0;i < n;++i) solve(i);

	vector<int> res;
	for (int i = 0;i < n;++i) for (int j = i+1;j < n;++j) {
		if (id[i][j] == -1) continue;
		if (state[i][j] == 1) res.pb(id[i][j]);
		DE(i, j, state[i][j]);
	}
	return res;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from simurgh.cpp:1:
simurgh.cpp: In function 'int get_cnt(std::vector<int>)':
simurgh.cpp:94:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |  assert(r.size() == n-1);
      |         ~~~~~~~~~^~~~~~
simurgh.cpp: In function 'void bs(std::vector<int>, int)':
simurgh.cpp:107:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for (int i = 0;i < part.size();++i)
      |                 ~~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:142:7: warning: unused variable 'cnt' [-Wunused-variable]
  142 |   int cnt = 0;
      |       ^~~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:209:3: note: in expansion of macro 'DE'
  209 |   DE(i, j, state[i][j]);
      |   ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 2 ms 332 KB correct
4 Correct 2 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 2 ms 332 KB correct
4 Correct 2 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 5 ms 460 KB correct
15 Correct 4 ms 588 KB correct
16 Correct 3 ms 460 KB correct
17 Correct 3 ms 460 KB correct
18 Correct 2 ms 460 KB correct
19 Correct 3 ms 512 KB correct
20 Correct 2 ms 460 KB correct
21 Correct 2 ms 460 KB correct
22 Correct 2 ms 460 KB correct
23 Correct 2 ms 460 KB correct
24 Correct 2 ms 460 KB correct
25 Correct 2 ms 460 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 2 ms 460 KB correct
28 Correct 2 ms 460 KB correct
29 Correct 2 ms 460 KB correct
30 Correct 3 ms 460 KB correct
31 Correct 2 ms 460 KB correct
32 Correct 2 ms 460 KB correct
33 Correct 3 ms 460 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 2 ms 332 KB correct
4 Correct 2 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 5 ms 460 KB correct
15 Correct 4 ms 588 KB correct
16 Correct 3 ms 460 KB correct
17 Correct 3 ms 460 KB correct
18 Correct 2 ms 460 KB correct
19 Correct 3 ms 512 KB correct
20 Correct 2 ms 460 KB correct
21 Correct 2 ms 460 KB correct
22 Correct 2 ms 460 KB correct
23 Correct 2 ms 460 KB correct
24 Correct 2 ms 460 KB correct
25 Correct 2 ms 460 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 2 ms 460 KB correct
28 Correct 2 ms 460 KB correct
29 Correct 2 ms 460 KB correct
30 Correct 3 ms 460 KB correct
31 Correct 2 ms 460 KB correct
32 Correct 2 ms 460 KB correct
33 Correct 3 ms 460 KB correct
34 Correct 70 ms 2120 KB correct
35 Correct 69 ms 2176 KB correct
36 Correct 57 ms 1868 KB correct
37 Correct 12 ms 1356 KB correct
38 Correct 74 ms 2180 KB correct
39 Correct 62 ms 1996 KB correct
40 Correct 56 ms 1868 KB correct
41 Correct 71 ms 2184 KB correct
42 Correct 73 ms 2120 KB correct
43 Correct 38 ms 1868 KB correct
44 Correct 34 ms 1740 KB correct
45 Correct 39 ms 1740 KB correct
46 Correct 30 ms 1740 KB correct
47 Correct 20 ms 1484 KB correct
48 Correct 6 ms 1356 KB correct
49 Correct 10 ms 1356 KB correct
50 Correct 18 ms 1556 KB correct
51 Correct 39 ms 1740 KB correct
52 Correct 41 ms 1740 KB correct
53 Correct 30 ms 1740 KB correct
54 Correct 50 ms 1868 KB correct
55 Correct 44 ms 1868 KB correct
56 Correct 43 ms 1868 KB correct
57 Correct 49 ms 1868 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 280 ms 4248 KB correct
4 Correct 466 ms 5640 KB correct
5 Correct 455 ms 5644 KB correct
6 Correct 457 ms 5640 KB correct
7 Correct 451 ms 5668 KB correct
8 Correct 399 ms 5648 KB correct
9 Correct 457 ms 5644 KB correct
10 Correct 473 ms 5640 KB correct
11 Correct 457 ms 5688 KB correct
12 Correct 445 ms 5640 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 449 ms 5636 KB correct
15 Correct 458 ms 5644 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 2 ms 332 KB correct
4 Correct 2 ms 332 KB correct
5 Correct 1 ms 332 KB correct
6 Correct 1 ms 332 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 332 KB correct
13 Correct 1 ms 332 KB correct
14 Correct 5 ms 460 KB correct
15 Correct 4 ms 588 KB correct
16 Correct 3 ms 460 KB correct
17 Correct 3 ms 460 KB correct
18 Correct 2 ms 460 KB correct
19 Correct 3 ms 512 KB correct
20 Correct 2 ms 460 KB correct
21 Correct 2 ms 460 KB correct
22 Correct 2 ms 460 KB correct
23 Correct 2 ms 460 KB correct
24 Correct 2 ms 460 KB correct
25 Correct 2 ms 460 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 2 ms 460 KB correct
28 Correct 2 ms 460 KB correct
29 Correct 2 ms 460 KB correct
30 Correct 3 ms 460 KB correct
31 Correct 2 ms 460 KB correct
32 Correct 2 ms 460 KB correct
33 Correct 3 ms 460 KB correct
34 Correct 70 ms 2120 KB correct
35 Correct 69 ms 2176 KB correct
36 Correct 57 ms 1868 KB correct
37 Correct 12 ms 1356 KB correct
38 Correct 74 ms 2180 KB correct
39 Correct 62 ms 1996 KB correct
40 Correct 56 ms 1868 KB correct
41 Correct 71 ms 2184 KB correct
42 Correct 73 ms 2120 KB correct
43 Correct 38 ms 1868 KB correct
44 Correct 34 ms 1740 KB correct
45 Correct 39 ms 1740 KB correct
46 Correct 30 ms 1740 KB correct
47 Correct 20 ms 1484 KB correct
48 Correct 6 ms 1356 KB correct
49 Correct 10 ms 1356 KB correct
50 Correct 18 ms 1556 KB correct
51 Correct 39 ms 1740 KB correct
52 Correct 41 ms 1740 KB correct
53 Correct 30 ms 1740 KB correct
54 Correct 50 ms 1868 KB correct
55 Correct 44 ms 1868 KB correct
56 Correct 43 ms 1868 KB correct
57 Correct 49 ms 1868 KB correct
58 Correct 1 ms 332 KB correct
59 Correct 1 ms 332 KB correct
60 Correct 280 ms 4248 KB correct
61 Correct 466 ms 5640 KB correct
62 Correct 455 ms 5644 KB correct
63 Correct 457 ms 5640 KB correct
64 Correct 451 ms 5668 KB correct
65 Correct 399 ms 5648 KB correct
66 Correct 457 ms 5644 KB correct
67 Correct 473 ms 5640 KB correct
68 Correct 457 ms 5688 KB correct
69 Correct 445 ms 5640 KB correct
70 Correct 1 ms 204 KB correct
71 Correct 449 ms 5636 KB correct
72 Correct 458 ms 5644 KB correct
73 Correct 1 ms 204 KB correct
74 Correct 442 ms 5644 KB correct
75 Correct 457 ms 6440 KB correct
76 Correct 167 ms 3652 KB correct
77 Correct 458 ms 6568 KB correct
78 Correct 452 ms 6628 KB correct
79 Correct 480 ms 6584 KB correct
80 Correct 475 ms 6444 KB correct
81 Correct 357 ms 5876 KB correct
82 Correct 444 ms 6444 KB correct
83 Correct 280 ms 4628 KB correct
84 Correct 268 ms 5072 KB correct
85 Correct 258 ms 4676 KB correct
86 Correct 203 ms 4072 KB correct
87 Correct 151 ms 3660 KB correct
88 Correct 114 ms 3424 KB correct
89 Correct 100 ms 3284 KB correct
90 Correct 88 ms 3272 KB correct
91 Correct 32 ms 2616 KB correct
92 Correct 14 ms 2572 KB correct
93 Correct 244 ms 4624 KB correct
94 Correct 178 ms 4092 KB correct
95 Correct 151 ms 3872 KB correct
96 Correct 93 ms 3272 KB correct
97 Correct 128 ms 3392 KB correct
98 Correct 126 ms 3568 KB correct
99 Correct 108 ms 3392 KB correct
100 Correct 54 ms 2752 KB correct
101 Correct 16 ms 2612 KB correct
102 Correct 314 ms 4660 KB correct
103 Correct 265 ms 4660 KB correct
104 Correct 271 ms 4668 KB correct
105 Correct 262 ms 4628 KB correct