oj.uz

Submission #415109

# Submission time Handle Problem Language Result Execution time Memory
415109 2021-05-31T14:35:46 Z Kevin_Zhang_TW Simurgh (IOI17_simurgh) C++17
70 / 100
 660 ms 5752 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]);

	bs(l, get_cnt(l));
	bs(r, get_cnt(r));
}

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:141:7: warning: unused variable 'cnt' [-Wunused-variable]
  141 |   int cnt = 0;
      |       ^~~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:208:3: note: in expansion of macro 'DE'
  208 |   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 1 ms 332 KB correct
4 Correct 1 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 1 ms 332 KB correct
4 Correct 1 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 4 ms 460 KB correct
15 Correct 3 ms 588 KB correct
16 Correct 4 ms 460 KB correct
17 Correct 4 ms 460 KB correct
18 Correct 3 ms 460 KB correct
19 Correct 3 ms 460 KB correct
20 Correct 3 ms 460 KB correct
21 Correct 3 ms 460 KB correct
22 Correct 3 ms 460 KB correct
23 Correct 4 ms 460 KB correct
24 Correct 2 ms 460 KB correct
25 Correct 1 ms 460 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 4 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 3 ms 460 KB correct
32 Correct 3 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 1 ms 332 KB correct
4 Correct 1 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 4 ms 460 KB correct
15 Correct 3 ms 588 KB correct
16 Correct 4 ms 460 KB correct
17 Correct 4 ms 460 KB correct
18 Correct 3 ms 460 KB correct
19 Correct 3 ms 460 KB correct
20 Correct 3 ms 460 KB correct
21 Correct 3 ms 460 KB correct
22 Correct 3 ms 460 KB correct
23 Correct 4 ms 460 KB correct
24 Correct 2 ms 460 KB correct
25 Correct 1 ms 460 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 4 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 3 ms 460 KB correct
32 Correct 3 ms 460 KB correct
33 Correct 3 ms 460 KB correct
34 Correct 90 ms 2180 KB correct
35 Correct 98 ms 2120 KB correct
36 Correct 71 ms 1868 KB correct
37 Correct 19 ms 1356 KB correct
38 Correct 90 ms 2184 KB correct
39 Correct 76 ms 1996 KB correct
40 Correct 69 ms 1868 KB correct
41 Correct 91 ms 2120 KB correct
42 Correct 93 ms 2120 KB correct
43 Correct 54 ms 1872 KB correct
44 Correct 46 ms 1740 KB correct
45 Correct 55 ms 1740 KB correct
46 Correct 43 ms 1740 KB correct
47 Correct 33 ms 1484 KB correct
48 Correct 5 ms 1356 KB correct
49 Correct 14 ms 1356 KB correct
50 Correct 27 ms 1560 KB correct
51 Correct 69 ms 1740 KB correct
52 Correct 49 ms 1740 KB correct
53 Correct 43 ms 1740 KB correct
54 Correct 56 ms 1868 KB correct
55 Correct 57 ms 1868 KB correct
56 Correct 56 ms 1868 KB correct
57 Correct 57 ms 1868 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 332 KB correct
3 Correct 319 ms 4292 KB correct
4 Correct 571 ms 5652 KB correct
5 Correct 574 ms 5644 KB correct
6 Correct 563 ms 5640 KB correct
7 Correct 448 ms 5640 KB correct
8 Correct 474 ms 5640 KB correct
9 Correct 660 ms 5752 KB correct
10 Correct 552 ms 5640 KB correct
11 Correct 555 ms 5648 KB correct
12 Correct 567 ms 5644 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 512 ms 5644 KB correct
15 Correct 582 ms 5688 KB correct

Subtask #5
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 1 ms 332 KB correct
4 Correct 1 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 4 ms 460 KB correct
15 Correct 3 ms 588 KB correct
16 Correct 4 ms 460 KB correct
17 Correct 4 ms 460 KB correct
18 Correct 3 ms 460 KB correct
19 Correct 3 ms 460 KB correct
20 Correct 3 ms 460 KB correct
21 Correct 3 ms 460 KB correct
22 Correct 3 ms 460 KB correct
23 Correct 4 ms 460 KB correct
24 Correct 2 ms 460 KB correct
25 Correct 1 ms 460 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 4 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 3 ms 460 KB correct
32 Correct 3 ms 460 KB correct
33 Correct 3 ms 460 KB correct
34 Correct 90 ms 2180 KB correct
35 Correct 98 ms 2120 KB correct
36 Correct 71 ms 1868 KB correct
37 Correct 19 ms 1356 KB correct
38 Correct 90 ms 2184 KB correct
39 Correct 76 ms 1996 KB correct
40 Correct 69 ms 1868 KB correct
41 Correct 91 ms 2120 KB correct
42 Correct 93 ms 2120 KB correct
43 Correct 54 ms 1872 KB correct
44 Correct 46 ms 1740 KB correct
45 Correct 55 ms 1740 KB correct
46 Correct 43 ms 1740 KB correct
47 Correct 33 ms 1484 KB correct
48 Correct 5 ms 1356 KB correct
49 Correct 14 ms 1356 KB correct
50 Correct 27 ms 1560 KB correct
51 Correct 69 ms 1740 KB correct
52 Correct 49 ms 1740 KB correct
53 Correct 43 ms 1740 KB correct
54 Correct 56 ms 1868 KB correct
55 Correct 57 ms 1868 KB correct
56 Correct 56 ms 1868 KB correct
57 Correct 57 ms 1868 KB correct
58 Correct 1 ms 204 KB correct
59 Correct 1 ms 332 KB correct
60 Correct 319 ms 4292 KB correct
61 Correct 571 ms 5652 KB correct
62 Correct 574 ms 5644 KB correct
63 Correct 563 ms 5640 KB correct
64 Correct 448 ms 5640 KB correct
65 Correct 474 ms 5640 KB correct
66 Correct 660 ms 5752 KB correct
67 Correct 552 ms 5640 KB correct
68 Correct 555 ms 5648 KB correct
69 Correct 567 ms 5644 KB correct
70 Correct 1 ms 204 KB correct
71 Correct 512 ms 5644 KB correct
72 Correct 582 ms 5688 KB correct
73 Correct 1 ms 204 KB correct
74 Incorrect 527 ms 5744 KB WA in grader: NO
75 Halted 0 ms 0 KB -