oj.uz

Submission #415107

# Submission time Handle Problem Language Result Execution time Memory
415107 2021-05-31T14:33:04 Z Kevin_Zhang_TW Simurgh (IOI17_simurgh) C++17
70 / 100
 605 ms 6572 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 qry(vector<int> r) { 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;
		DE(a, b, state[a][b]);
	}

	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:92:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |  assert(r.size() == n-1);
      |         ~~~~~~~~~^~~~~~
simurgh.cpp: In function 'void bs(std::vector<int>, int)':
simurgh.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  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:139:7: warning: unused variable 'cnt' [-Wunused-variable]
  139 |   int cnt = 0;
      |       ^~~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:195:3: note: in expansion of macro 'DE'
  195 |   DE(a, b, state[a][b]);
      |   ^~
simurgh.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
simurgh.cpp:204:3: note: in expansion of macro 'DE'
  204 |   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 296 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 2 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 292 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 296 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 2 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 292 KB correct
14 Correct 3 ms 588 KB correct
15 Correct 3 ms 588 KB correct
16 Correct 4 ms 588 KB correct
17 Correct 3 ms 568 KB correct
18 Correct 2 ms 460 KB correct
19 Correct 3 ms 588 KB correct
20 Correct 3 ms 460 KB correct
21 Correct 4 ms 460 KB correct
22 Correct 3 ms 564 KB correct
23 Correct 2 ms 460 KB correct
24 Correct 3 ms 588 KB correct
25 Correct 1 ms 436 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 3 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 2 ms 460 KB correct
33 Correct 2 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 296 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 2 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 292 KB correct
14 Correct 3 ms 588 KB correct
15 Correct 3 ms 588 KB correct
16 Correct 4 ms 588 KB correct
17 Correct 3 ms 568 KB correct
18 Correct 2 ms 460 KB correct
19 Correct 3 ms 588 KB correct
20 Correct 3 ms 460 KB correct
21 Correct 4 ms 460 KB correct
22 Correct 3 ms 564 KB correct
23 Correct 2 ms 460 KB correct
24 Correct 3 ms 588 KB correct
25 Correct 1 ms 436 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 3 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 2 ms 460 KB correct
33 Correct 2 ms 460 KB correct
34 Correct 89 ms 2364 KB correct
35 Correct 98 ms 2372 KB correct
36 Correct 71 ms 2120 KB correct
37 Correct 17 ms 1468 KB correct
38 Correct 97 ms 2376 KB correct
39 Correct 81 ms 2248 KB correct
40 Correct 66 ms 2120 KB correct
41 Correct 112 ms 2364 KB correct
42 Correct 99 ms 2384 KB correct
43 Correct 53 ms 1996 KB correct
44 Correct 48 ms 1856 KB correct
45 Correct 52 ms 1920 KB correct
46 Correct 47 ms 1776 KB correct
47 Correct 28 ms 1484 KB correct
48 Correct 5 ms 1328 KB correct
49 Correct 13 ms 1456 KB correct
50 Correct 26 ms 1484 KB correct
51 Correct 50 ms 1868 KB correct
52 Correct 50 ms 1892 KB correct
53 Correct 42 ms 1740 KB correct
54 Correct 61 ms 1996 KB correct
55 Correct 78 ms 1928 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 329 ms 4256 KB correct
4 Correct 581 ms 5644 KB correct
5 Correct 605 ms 5560 KB correct
6 Correct 544 ms 5684 KB correct
7 Correct 470 ms 5640 KB correct
8 Correct 451 ms 5688 KB correct
9 Correct 558 ms 5644 KB correct
10 Correct 576 ms 5644 KB correct
11 Correct 571 ms 5644 KB correct
12 Correct 554 ms 5644 KB correct
13 Correct 1 ms 204 KB correct
14 Correct 496 ms 5636 KB correct
15 Correct 572 ms 5640 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 296 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 2 ms 332 KB correct
10 Correct 1 ms 332 KB correct
11 Correct 1 ms 332 KB correct
12 Correct 1 ms 300 KB correct
13 Correct 1 ms 292 KB correct
14 Correct 3 ms 588 KB correct
15 Correct 3 ms 588 KB correct
16 Correct 4 ms 588 KB correct
17 Correct 3 ms 568 KB correct
18 Correct 2 ms 460 KB correct
19 Correct 3 ms 588 KB correct
20 Correct 3 ms 460 KB correct
21 Correct 4 ms 460 KB correct
22 Correct 3 ms 564 KB correct
23 Correct 2 ms 460 KB correct
24 Correct 3 ms 588 KB correct
25 Correct 1 ms 436 KB correct
26 Correct 2 ms 460 KB correct
27 Correct 3 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 2 ms 460 KB correct
33 Correct 2 ms 460 KB correct
34 Correct 89 ms 2364 KB correct
35 Correct 98 ms 2372 KB correct
36 Correct 71 ms 2120 KB correct
37 Correct 17 ms 1468 KB correct
38 Correct 97 ms 2376 KB correct
39 Correct 81 ms 2248 KB correct
40 Correct 66 ms 2120 KB correct
41 Correct 112 ms 2364 KB correct
42 Correct 99 ms 2384 KB correct
43 Correct 53 ms 1996 KB correct
44 Correct 48 ms 1856 KB correct
45 Correct 52 ms 1920 KB correct
46 Correct 47 ms 1776 KB correct
47 Correct 28 ms 1484 KB correct
48 Correct 5 ms 1328 KB correct
49 Correct 13 ms 1456 KB correct
50 Correct 26 ms 1484 KB correct
51 Correct 50 ms 1868 KB correct
52 Correct 50 ms 1892 KB correct
53 Correct 42 ms 1740 KB correct
54 Correct 61 ms 1996 KB correct
55 Correct 78 ms 1928 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 329 ms 4256 KB correct
61 Correct 581 ms 5644 KB correct
62 Correct 605 ms 5560 KB correct
63 Correct 544 ms 5684 KB correct
64 Correct 470 ms 5640 KB correct
65 Correct 451 ms 5688 KB correct
66 Correct 558 ms 5644 KB correct
67 Correct 576 ms 5644 KB correct
68 Correct 571 ms 5644 KB correct
69 Correct 554 ms 5644 KB correct
70 Correct 1 ms 204 KB correct
71 Correct 496 ms 5636 KB correct
72 Correct 572 ms 5640 KB correct
73 Correct 1 ms 332 KB correct
74 Incorrect 544 ms 6572 KB WA in grader: NO
75 Halted 0 ms 0 KB -