# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
274843 |
2020-08-19T16:42:22 Z |
junseo |
Simurgh (IOI17_simurgh) |
C++17 |
|
388 ms |
9580 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define rmin(r, x) r = min(r, x);
#define rmax(r, x) r = max(r, x);
#define ends ' '
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0), cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn = 505;
const int maxm = maxn * maxn;
int n, m, K;
pii pa[maxn];
bool visited[maxn], used[maxm];
int gold[maxm], k[maxm], h[maxn];
vector<pii> edge, adj[maxn], ch[maxn], bk[maxn], rbk[maxn];
vector<int> dfs_tree;
int count_common_roads(const vector<int>& r);
int count_k(vector<int> v, vector<pii> rep) {
vector<int> q;
for(auto [add, sub] : rep) q.eb(add);
int i = 0, j = 0;
while(i < v.size()) {
if(j < rep.size() && v[i] == rep[j].se) {
++i;
++j;
continue;
}
q.eb(v[i++]);
}
return count_common_roads(q);
}
void dfs(int u, int p) {
visited[u] = true;
for(auto [v, i] : adj[u]) if(v != p && !used[i]) {
used[i] = true;
if(visited[v]) {
bk[u].eb(i, ch[v].back().se);
rbk[v].eb(u, i);
continue;
}
dfs_tree.eb(i);
ch[u].eb(v, i);
pa[v] = {u, i};
h[v] = h[u] + 1;
dfs(v, u);
}
}
void solve_tree(int u) {
sort(all(rbk[u]), [&](pii a, pii b) { return h[a.fi] > h[b.fi]; });
for(auto [v, i] : rbk[u]) {
vector<int> tedge;
bool all = true, no = true;
while(v != u) {
tedge.eb(pa[v].se);
if(gold[tedge.back()] != -1) all = false;
else no = false;
v = pa[v].fi;
}
if(no) continue;
if(all) {
int nk = n, xk = 0;
for(auto j : tedge) {
vector<pii> dum; dum.eb(i, j);
k[j] = count_k(dfs_tree, dum);
rmin(nk, k[j]);
rmax(xk, k[j]);
}
if(nk != xk) {
gold[i] = nk - (K - 1);
for(auto j : tedge) gold[j] = (nk == k[j]);
}
else {
if(nk == K - 1) {
for(auto j : tedge) gold[j] = true;
gold[i] = false;
}
else for(auto j : tedge) gold[j] = false;
}
}
else {
for(auto j : tedge) if(gold[j] != -1) {
vector<pii> dum; dum.eb(i, j);
gold[i] = count_k(dfs_tree, dum) - K + gold[j];
break;
}
for(auto j : tedge) if(gold[j] == -1) {
vector<pii> dum; dum.eb(i, j);
gold[j] = K + gold[i] - count_k(dfs_tree, dum);
}
}
}
for(auto [v, i] : ch[u]) solve_tree(v);
}
void solve_back(vector<pii> e, int l, int r, int cnt) {
// count_k = K - S(gold[sub]) + S(gold[add])
// S(gold[add]) = count_k - K + S(gold[sub])
if(l > r) return;
if(cnt == 0) {
for(auto [add, sub] : e) gold[add] = false;
return;
}
if(cnt == r - l + 1) {
for(auto [add, sub] : e) gold[add] = true;
return;
}
int mid = l + r >> 1;
vector<pii> t;
for(int i = mid + 1; i <= r; ++i) {
t.eb(e.back());
e.pop_back();
}
reverse(all(t));
int ret = count_k(dfs_tree, e) - K;
for(auto [add, sub] : e) ret += gold[sub];
solve_back(e, l, mid, ret);
solve_back(t, mid + 1, r, cnt - ret);
}
std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
n = _n, m = u.size();
for(int i = 0; i < m; ++i) {
edge.eb(u[i], v[i]);
adj[u[i]].eb(v[i], i);
adj[v[i]].eb(u[i], i);
}
dfs(0, -1);
sort(all(dfs_tree));
K = count_k(dfs_tree, vector<pii>());
memset(gold, -1, sizeof(gold));
solve_tree(0);
for(int i = 0; i < n; ++i) if(!bk[i].empty()) {
sort(all(bk[i]), [](pii a, pii b) { return a.se < b.se; });
vector<pii> v;
for(auto t : bk[i]) if(gold[t.fi] == -1) v.eb(t);
if(!v.empty()) {
int cnt = count_k(dfs_tree, v) - K;
for(auto [add, sub] : v) cnt += gold[sub];
solve_back(v, 0, v.size() - 1, cnt);
}
}
vector<int> ans;
for(int i = 0; i < m; ++i) if(gold[i]) ans.eb(i);
return ans;
}
Compilation message
simurgh.cpp: In function 'int count_k(std::vector<int>, std::vector<std::pair<int, int> >)':
simurgh.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | while(i < v.size()) {
| ~~^~~~~~~~~~
simurgh.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if(j < rep.size() && v[i] == rep[j].se) {
| ~~^~~~~~~~~~~~
simurgh.cpp: In function 'void solve_back(std::vector<std::pair<int, int> >, int, int, int)':
simurgh.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
123 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1408 KB |
correct |
2 |
Correct |
1 ms |
1408 KB |
correct |
3 |
Correct |
1 ms |
1408 KB |
correct |
4 |
Correct |
1 ms |
1408 KB |
correct |
5 |
Correct |
1 ms |
1408 KB |
correct |
6 |
Correct |
1 ms |
1408 KB |
correct |
7 |
Correct |
1 ms |
1408 KB |
correct |
8 |
Correct |
1 ms |
1408 KB |
correct |
9 |
Correct |
1 ms |
1408 KB |
correct |
10 |
Correct |
1 ms |
1408 KB |
correct |
11 |
Correct |
1 ms |
1408 KB |
correct |
12 |
Correct |
1 ms |
1408 KB |
correct |
13 |
Correct |
1 ms |
1408 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1408 KB |
correct |
2 |
Correct |
1 ms |
1408 KB |
correct |
3 |
Correct |
1 ms |
1408 KB |
correct |
4 |
Correct |
1 ms |
1408 KB |
correct |
5 |
Correct |
1 ms |
1408 KB |
correct |
6 |
Correct |
1 ms |
1408 KB |
correct |
7 |
Correct |
1 ms |
1408 KB |
correct |
8 |
Correct |
1 ms |
1408 KB |
correct |
9 |
Correct |
1 ms |
1408 KB |
correct |
10 |
Correct |
1 ms |
1408 KB |
correct |
11 |
Correct |
1 ms |
1408 KB |
correct |
12 |
Correct |
1 ms |
1408 KB |
correct |
13 |
Correct |
1 ms |
1408 KB |
correct |
14 |
Correct |
3 ms |
1536 KB |
correct |
15 |
Correct |
3 ms |
1536 KB |
correct |
16 |
Correct |
3 ms |
1536 KB |
correct |
17 |
Correct |
3 ms |
1408 KB |
correct |
18 |
Correct |
2 ms |
1408 KB |
correct |
19 |
Correct |
3 ms |
1408 KB |
correct |
20 |
Correct |
2 ms |
1408 KB |
correct |
21 |
Correct |
2 ms |
1408 KB |
correct |
22 |
Correct |
2 ms |
1408 KB |
correct |
23 |
Correct |
2 ms |
1408 KB |
correct |
24 |
Correct |
2 ms |
1408 KB |
correct |
25 |
Correct |
2 ms |
1408 KB |
correct |
26 |
Correct |
3 ms |
1408 KB |
correct |
27 |
Correct |
2 ms |
1408 KB |
correct |
28 |
Correct |
2 ms |
1408 KB |
correct |
29 |
Correct |
2 ms |
1408 KB |
correct |
30 |
Correct |
2 ms |
1408 KB |
correct |
31 |
Correct |
3 ms |
1408 KB |
correct |
32 |
Correct |
3 ms |
1408 KB |
correct |
33 |
Correct |
2 ms |
1408 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1408 KB |
correct |
2 |
Correct |
1 ms |
1408 KB |
correct |
3 |
Correct |
1 ms |
1408 KB |
correct |
4 |
Correct |
1 ms |
1408 KB |
correct |
5 |
Correct |
1 ms |
1408 KB |
correct |
6 |
Correct |
1 ms |
1408 KB |
correct |
7 |
Correct |
1 ms |
1408 KB |
correct |
8 |
Correct |
1 ms |
1408 KB |
correct |
9 |
Correct |
1 ms |
1408 KB |
correct |
10 |
Correct |
1 ms |
1408 KB |
correct |
11 |
Correct |
1 ms |
1408 KB |
correct |
12 |
Correct |
1 ms |
1408 KB |
correct |
13 |
Correct |
1 ms |
1408 KB |
correct |
14 |
Correct |
3 ms |
1536 KB |
correct |
15 |
Correct |
3 ms |
1536 KB |
correct |
16 |
Correct |
3 ms |
1536 KB |
correct |
17 |
Correct |
3 ms |
1408 KB |
correct |
18 |
Correct |
2 ms |
1408 KB |
correct |
19 |
Correct |
3 ms |
1408 KB |
correct |
20 |
Correct |
2 ms |
1408 KB |
correct |
21 |
Correct |
2 ms |
1408 KB |
correct |
22 |
Correct |
2 ms |
1408 KB |
correct |
23 |
Correct |
2 ms |
1408 KB |
correct |
24 |
Correct |
2 ms |
1408 KB |
correct |
25 |
Correct |
2 ms |
1408 KB |
correct |
26 |
Correct |
3 ms |
1408 KB |
correct |
27 |
Correct |
2 ms |
1408 KB |
correct |
28 |
Correct |
2 ms |
1408 KB |
correct |
29 |
Correct |
2 ms |
1408 KB |
correct |
30 |
Correct |
2 ms |
1408 KB |
correct |
31 |
Correct |
3 ms |
1408 KB |
correct |
32 |
Correct |
3 ms |
1408 KB |
correct |
33 |
Correct |
2 ms |
1408 KB |
correct |
34 |
Correct |
58 ms |
3324 KB |
correct |
35 |
Correct |
57 ms |
3316 KB |
correct |
36 |
Correct |
50 ms |
2948 KB |
correct |
37 |
Correct |
10 ms |
1536 KB |
correct |
38 |
Correct |
59 ms |
3324 KB |
correct |
39 |
Correct |
51 ms |
3188 KB |
correct |
40 |
Correct |
43 ms |
2940 KB |
correct |
41 |
Correct |
54 ms |
3452 KB |
correct |
42 |
Correct |
55 ms |
3324 KB |
correct |
43 |
Correct |
30 ms |
2560 KB |
correct |
44 |
Correct |
22 ms |
2304 KB |
correct |
45 |
Correct |
25 ms |
2432 KB |
correct |
46 |
Correct |
21 ms |
2176 KB |
correct |
47 |
Correct |
12 ms |
1792 KB |
correct |
48 |
Correct |
4 ms |
1408 KB |
correct |
49 |
Correct |
7 ms |
1536 KB |
correct |
50 |
Correct |
13 ms |
1792 KB |
correct |
51 |
Correct |
27 ms |
2304 KB |
correct |
52 |
Correct |
22 ms |
2304 KB |
correct |
53 |
Correct |
21 ms |
2176 KB |
correct |
54 |
Correct |
27 ms |
2560 KB |
correct |
55 |
Correct |
32 ms |
2432 KB |
correct |
56 |
Correct |
29 ms |
2432 KB |
correct |
57 |
Correct |
28 ms |
2432 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1408 KB |
correct |
2 |
Correct |
1 ms |
1408 KB |
correct |
3 |
Correct |
202 ms |
7148 KB |
correct |
4 |
Correct |
338 ms |
9452 KB |
correct |
5 |
Correct |
339 ms |
9452 KB |
correct |
6 |
Correct |
339 ms |
9452 KB |
correct |
7 |
Correct |
312 ms |
9452 KB |
correct |
8 |
Correct |
302 ms |
9452 KB |
correct |
9 |
Correct |
337 ms |
9580 KB |
correct |
10 |
Correct |
349 ms |
9340 KB |
correct |
11 |
Correct |
346 ms |
9336 KB |
correct |
12 |
Correct |
368 ms |
9324 KB |
correct |
13 |
Correct |
1 ms |
1408 KB |
correct |
14 |
Correct |
326 ms |
9340 KB |
correct |
15 |
Correct |
383 ms |
9536 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1408 KB |
correct |
2 |
Correct |
1 ms |
1408 KB |
correct |
3 |
Correct |
1 ms |
1408 KB |
correct |
4 |
Correct |
1 ms |
1408 KB |
correct |
5 |
Correct |
1 ms |
1408 KB |
correct |
6 |
Correct |
1 ms |
1408 KB |
correct |
7 |
Correct |
1 ms |
1408 KB |
correct |
8 |
Correct |
1 ms |
1408 KB |
correct |
9 |
Correct |
1 ms |
1408 KB |
correct |
10 |
Correct |
1 ms |
1408 KB |
correct |
11 |
Correct |
1 ms |
1408 KB |
correct |
12 |
Correct |
1 ms |
1408 KB |
correct |
13 |
Correct |
1 ms |
1408 KB |
correct |
14 |
Correct |
3 ms |
1536 KB |
correct |
15 |
Correct |
3 ms |
1536 KB |
correct |
16 |
Correct |
3 ms |
1536 KB |
correct |
17 |
Correct |
3 ms |
1408 KB |
correct |
18 |
Correct |
2 ms |
1408 KB |
correct |
19 |
Correct |
3 ms |
1408 KB |
correct |
20 |
Correct |
2 ms |
1408 KB |
correct |
21 |
Correct |
2 ms |
1408 KB |
correct |
22 |
Correct |
2 ms |
1408 KB |
correct |
23 |
Correct |
2 ms |
1408 KB |
correct |
24 |
Correct |
2 ms |
1408 KB |
correct |
25 |
Correct |
2 ms |
1408 KB |
correct |
26 |
Correct |
3 ms |
1408 KB |
correct |
27 |
Correct |
2 ms |
1408 KB |
correct |
28 |
Correct |
2 ms |
1408 KB |
correct |
29 |
Correct |
2 ms |
1408 KB |
correct |
30 |
Correct |
2 ms |
1408 KB |
correct |
31 |
Correct |
3 ms |
1408 KB |
correct |
32 |
Correct |
3 ms |
1408 KB |
correct |
33 |
Correct |
2 ms |
1408 KB |
correct |
34 |
Correct |
58 ms |
3324 KB |
correct |
35 |
Correct |
57 ms |
3316 KB |
correct |
36 |
Correct |
50 ms |
2948 KB |
correct |
37 |
Correct |
10 ms |
1536 KB |
correct |
38 |
Correct |
59 ms |
3324 KB |
correct |
39 |
Correct |
51 ms |
3188 KB |
correct |
40 |
Correct |
43 ms |
2940 KB |
correct |
41 |
Correct |
54 ms |
3452 KB |
correct |
42 |
Correct |
55 ms |
3324 KB |
correct |
43 |
Correct |
30 ms |
2560 KB |
correct |
44 |
Correct |
22 ms |
2304 KB |
correct |
45 |
Correct |
25 ms |
2432 KB |
correct |
46 |
Correct |
21 ms |
2176 KB |
correct |
47 |
Correct |
12 ms |
1792 KB |
correct |
48 |
Correct |
4 ms |
1408 KB |
correct |
49 |
Correct |
7 ms |
1536 KB |
correct |
50 |
Correct |
13 ms |
1792 KB |
correct |
51 |
Correct |
27 ms |
2304 KB |
correct |
52 |
Correct |
22 ms |
2304 KB |
correct |
53 |
Correct |
21 ms |
2176 KB |
correct |
54 |
Correct |
27 ms |
2560 KB |
correct |
55 |
Correct |
32 ms |
2432 KB |
correct |
56 |
Correct |
29 ms |
2432 KB |
correct |
57 |
Correct |
28 ms |
2432 KB |
correct |
58 |
Correct |
1 ms |
1408 KB |
correct |
59 |
Correct |
1 ms |
1408 KB |
correct |
60 |
Correct |
202 ms |
7148 KB |
correct |
61 |
Correct |
338 ms |
9452 KB |
correct |
62 |
Correct |
339 ms |
9452 KB |
correct |
63 |
Correct |
339 ms |
9452 KB |
correct |
64 |
Correct |
312 ms |
9452 KB |
correct |
65 |
Correct |
302 ms |
9452 KB |
correct |
66 |
Correct |
337 ms |
9580 KB |
correct |
67 |
Correct |
349 ms |
9340 KB |
correct |
68 |
Correct |
346 ms |
9336 KB |
correct |
69 |
Correct |
368 ms |
9324 KB |
correct |
70 |
Correct |
1 ms |
1408 KB |
correct |
71 |
Correct |
326 ms |
9340 KB |
correct |
72 |
Correct |
383 ms |
9536 KB |
correct |
73 |
Correct |
1 ms |
1408 KB |
correct |
74 |
Correct |
388 ms |
9580 KB |
correct |
75 |
Correct |
333 ms |
9196 KB |
correct |
76 |
Correct |
129 ms |
4472 KB |
correct |
77 |
Correct |
340 ms |
9324 KB |
correct |
78 |
Correct |
340 ms |
9456 KB |
correct |
79 |
Correct |
348 ms |
9528 KB |
correct |
80 |
Correct |
347 ms |
9196 KB |
correct |
81 |
Correct |
301 ms |
8812 KB |
correct |
82 |
Correct |
357 ms |
9324 KB |
correct |
83 |
Correct |
201 ms |
5744 KB |
correct |
84 |
Correct |
157 ms |
6892 KB |
correct |
85 |
Correct |
141 ms |
6384 KB |
correct |
86 |
Correct |
102 ms |
4600 KB |
correct |
87 |
Correct |
75 ms |
3836 KB |
correct |
88 |
Correct |
60 ms |
3196 KB |
correct |
89 |
Correct |
60 ms |
3188 KB |
correct |
90 |
Correct |
55 ms |
2940 KB |
correct |
91 |
Correct |
22 ms |
1664 KB |
correct |
92 |
Correct |
14 ms |
1536 KB |
correct |
93 |
Correct |
136 ms |
6384 KB |
correct |
94 |
Correct |
94 ms |
4600 KB |
correct |
95 |
Correct |
92 ms |
4720 KB |
correct |
96 |
Correct |
64 ms |
3316 KB |
correct |
97 |
Correct |
62 ms |
3196 KB |
correct |
98 |
Correct |
70 ms |
3836 KB |
correct |
99 |
Correct |
63 ms |
3376 KB |
correct |
100 |
Correct |
31 ms |
1920 KB |
correct |
101 |
Correct |
16 ms |
1536 KB |
correct |
102 |
Correct |
163 ms |
5488 KB |
correct |
103 |
Correct |
167 ms |
5488 KB |
correct |
104 |
Correct |
166 ms |
5488 KB |
correct |
105 |
Correct |
163 ms |
5488 KB |
correct |