# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
640393 |
2022-09-14T14:16:07 Z |
chenwz |
Parking (CEOI22_parking) |
C++11 |
|
471 ms |
85360 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 400005;
int b[MAXN], t[MAXN], fa[MAXN], siz[MAXN], InCycle[MAXN], TPCnt[MAXN],
cnt[MAXN];
set<int> Free, G[MAXN];
vector<int> Loc[MAXN];
vector<pair<pi, int> > red;
vector<pi> sol;
void move(int x, int y) {
sol.push_back({x, y});
if (++cnt[y] == 1) Free.erase(y);
if (--cnt[x] == 0) Free.insert(x);
}
int find_set(int x) { return x == fa[x] ? x : fa[x] = find_set(fa[x]); }
void add_edge(int x, int y) {
G[x].insert(y), G[y].insert(x);
TPCnt[y] += (x % 2) && (y % 2);
x = find_set(x), y = find_set(y);
if (x == y)
InCycle[x] = 1;
else
fa[x] = y, siz[y] += siz[x], TPCnt[y] += TPCnt[x];
}
void remove_edge(int x, int y) { G[x].erase(y), G[y].erase(x); }
int get_end_of_chain(int x, int last) {
if (G[x].size() == 1) return x;
assert(G[x].size() == 2);
for (auto v : G[x])
if (v != last) return get_end_of_chain(v, x);
return -1;
}
bool solve_path(int idx) {
int curr = get_end_of_chain(idx, -1), last = -1;
vector<int> r;
while (curr != -1) {
r.push_back(curr);
int nxt = -1;
for (auto v : G[curr])
if (v != last) nxt = v;
last = curr, curr = nxt;
}
for (int i = 0, sz = r.size(); i < sz; i++) {
if (r[i + 1] % 2 == 1) {
move(r[i + 1] / 2, r[i] / 2), i++;
continue;
}
int k = -1;
for (int j = i; j < sz - 1; j++) {
if (r[j] % 2 == 1 && r[j + 1] % 2 == 1) {
k = j;
break;
}
}
if (k != -1) {
if (Free.empty()) return false;
int to = *Free.begin();
move(r[k] / 2, to), move(r[k + 1] / 2, to);
for (int j = k - 1; j >= i; j -= 2) move(r[j - 1] / 2, r[j] / 2);
i = k + 1;
} else {
for (int j = sz - 1; j > i + 1; j -= 2) move(r[j - 1] / 2, r[j] / 2);
move(r[i] / 2, r[i + 1] / 2);
break;
}
}
return true;
}
bool solve_cycle(int idx) {
if (Free.empty()) return false;
int pocetak = idx, curr = idx, last = -1;
vector<int> r;
while (curr != -1) {
r.push_back(curr);
int nxt = -1;
for (auto v : G[curr]) {
if (v == last || v == pocetak) continue;
nxt = v;
}
last = curr, curr = nxt;
}
int R = r.size(), k = -1;
for (int i = 0; i < R; i++) {
if (r[i] % 2 == 1) k = i;
if (r[i] % 2 == 1 && r[(i + 1) % R] % 2 == 1) {
k = i;
break;
}
}
int x = r[k], y = r[(k + 1) % R];
if (y % 2 == 1) {
int to = *Free.begin();
move(x / 2, to), move(y / 2, to);
remove_edge(r[(k - 1 + R) % R], r[k]);
remove_edge(r[k], r[(k + 1) % R]);
remove_edge(r[(k + 1) % R], r[(k + 2) % R]);
solve_path(r[(k + 2) % r.size()]);
} else {
int to = *Free.begin();
if (x / 2 != y / 2) {
move(x / 2, to);
for (int i = 2; i < R; i += 2)
move(r[(k - i + R) % R] / 2, r[(k - i + 1 + R) % R] / 2);
move(y / 2, to);
} else {
move(x / 2, to);
for (int i = 1; i + 1 < R; i += 2)
move(r[(k + i + 1) % R] / 2, r[(k + i) % R] / 2);
move(r[(k - 1 + R) % R] / 2, to);
}
}
return true;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> b[i] >> t[i];
if (b[i]) Loc[b[i]].push_back(2 * i);
if (t[i]) Loc[t[i]].push_back(2 * i + 1);
fa[2 * i] = 2 * i, siz[2 * i] = 1;
fa[2 * i + 1] = 2 * i + 1, siz[2 * i + 1] = 1;
cnt[i] = (b[i] > 0) + (t[i] > 0);
if (cnt[i] == 0) Free.insert(i);
}
for (int i = 1; i <= n; i++) {
int x = Loc[i][0], y = Loc[i][1];
if (x / 2 != y / 2) add_edge(x, y);
}
for (int i = 0; i < m; i++)
if (b[i] && t[i] && b[i] != t[i]) add_edge(2 * i, 2 * i + 1);
for (int i = 0; i < 2 * m; i++)
if (i == fa[i] && siz[i] > 1) red.push_back({{InCycle[i], TPCnt[i]}, i});
sort(red.begin(), red.end());
bool suc = true;
for (auto p : red) {
int idx = p.second;
suc = !InCycle[idx] ? solve_path(idx) : solve_cycle(idx);
if (!suc) break;
}
if (!suc) {
cout << -1 << '\n';
} else {
cout << sol.size() << endl;
for (auto p : sol) cout << p.first + 1 << " " << p.second + 1 << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
28500 KB |
Output is correct |
2 |
Correct |
15 ms |
28500 KB |
Output is correct |
3 |
Correct |
14 ms |
28500 KB |
Output is correct |
4 |
Correct |
15 ms |
28500 KB |
Output is correct |
5 |
Correct |
15 ms |
28472 KB |
Output is correct |
6 |
Correct |
14 ms |
28500 KB |
Output is correct |
7 |
Correct |
15 ms |
28500 KB |
Output is correct |
8 |
Correct |
14 ms |
28500 KB |
Output is correct |
9 |
Correct |
15 ms |
28428 KB |
Output is correct |
10 |
Correct |
16 ms |
28500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
194 ms |
55816 KB |
Output is correct |
2 |
Correct |
246 ms |
59320 KB |
Output is correct |
3 |
Correct |
155 ms |
52204 KB |
Output is correct |
4 |
Correct |
142 ms |
51540 KB |
Output is correct |
5 |
Correct |
237 ms |
59152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
28628 KB |
Output is correct |
2 |
Correct |
15 ms |
28500 KB |
Output is correct |
3 |
Correct |
16 ms |
28768 KB |
Output is correct |
4 |
Correct |
16 ms |
28820 KB |
Output is correct |
5 |
Correct |
16 ms |
28724 KB |
Output is correct |
6 |
Correct |
17 ms |
28884 KB |
Output is correct |
7 |
Correct |
17 ms |
28756 KB |
Output is correct |
8 |
Correct |
14 ms |
28748 KB |
Output is correct |
9 |
Correct |
21 ms |
28816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
28628 KB |
Output is correct |
2 |
Correct |
15 ms |
28500 KB |
Output is correct |
3 |
Correct |
16 ms |
28768 KB |
Output is correct |
4 |
Correct |
16 ms |
28820 KB |
Output is correct |
5 |
Correct |
16 ms |
28724 KB |
Output is correct |
6 |
Correct |
17 ms |
28884 KB |
Output is correct |
7 |
Correct |
17 ms |
28756 KB |
Output is correct |
8 |
Correct |
14 ms |
28748 KB |
Output is correct |
9 |
Correct |
21 ms |
28816 KB |
Output is correct |
10 |
Correct |
471 ms |
85360 KB |
Output is correct |
11 |
Correct |
83 ms |
39864 KB |
Output is correct |
12 |
Correct |
324 ms |
78212 KB |
Output is correct |
13 |
Correct |
439 ms |
82696 KB |
Output is correct |
14 |
Correct |
316 ms |
80320 KB |
Output is correct |
15 |
Correct |
318 ms |
78344 KB |
Output is correct |
16 |
Correct |
462 ms |
85296 KB |
Output is correct |
17 |
Correct |
365 ms |
78768 KB |
Output is correct |
18 |
Correct |
464 ms |
84480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28756 KB |
Output is correct |
2 |
Correct |
17 ms |
28756 KB |
Output is correct |
3 |
Correct |
16 ms |
28680 KB |
Output is correct |
4 |
Correct |
18 ms |
28628 KB |
Output is correct |
5 |
Correct |
18 ms |
28540 KB |
Output is correct |
6 |
Correct |
17 ms |
28740 KB |
Output is correct |
7 |
Correct |
20 ms |
28756 KB |
Output is correct |
8 |
Correct |
18 ms |
28796 KB |
Output is correct |
9 |
Correct |
15 ms |
28740 KB |
Output is correct |
10 |
Correct |
15 ms |
28756 KB |
Output is correct |
11 |
Correct |
15 ms |
28756 KB |
Output is correct |
12 |
Correct |
16 ms |
28756 KB |
Output is correct |
13 |
Correct |
15 ms |
28756 KB |
Output is correct |
14 |
Correct |
17 ms |
28772 KB |
Output is correct |
15 |
Correct |
14 ms |
28756 KB |
Output is correct |
16 |
Correct |
16 ms |
28880 KB |
Output is correct |
17 |
Correct |
16 ms |
28804 KB |
Output is correct |
18 |
Correct |
16 ms |
28728 KB |
Output is correct |
19 |
Correct |
17 ms |
28756 KB |
Output is correct |
20 |
Correct |
16 ms |
28740 KB |
Output is correct |
21 |
Correct |
16 ms |
28756 KB |
Output is correct |
22 |
Correct |
16 ms |
28756 KB |
Output is correct |
23 |
Correct |
18 ms |
28756 KB |
Output is correct |
24 |
Correct |
18 ms |
28756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
28500 KB |
Output is correct |
2 |
Correct |
15 ms |
28500 KB |
Output is correct |
3 |
Correct |
14 ms |
28500 KB |
Output is correct |
4 |
Correct |
15 ms |
28500 KB |
Output is correct |
5 |
Correct |
15 ms |
28472 KB |
Output is correct |
6 |
Correct |
14 ms |
28500 KB |
Output is correct |
7 |
Correct |
15 ms |
28500 KB |
Output is correct |
8 |
Correct |
14 ms |
28500 KB |
Output is correct |
9 |
Correct |
15 ms |
28428 KB |
Output is correct |
10 |
Correct |
16 ms |
28500 KB |
Output is correct |
11 |
Correct |
194 ms |
55816 KB |
Output is correct |
12 |
Correct |
246 ms |
59320 KB |
Output is correct |
13 |
Correct |
155 ms |
52204 KB |
Output is correct |
14 |
Correct |
142 ms |
51540 KB |
Output is correct |
15 |
Correct |
237 ms |
59152 KB |
Output is correct |
16 |
Correct |
20 ms |
28628 KB |
Output is correct |
17 |
Correct |
15 ms |
28500 KB |
Output is correct |
18 |
Correct |
16 ms |
28768 KB |
Output is correct |
19 |
Correct |
16 ms |
28820 KB |
Output is correct |
20 |
Correct |
16 ms |
28724 KB |
Output is correct |
21 |
Correct |
17 ms |
28884 KB |
Output is correct |
22 |
Correct |
17 ms |
28756 KB |
Output is correct |
23 |
Correct |
14 ms |
28748 KB |
Output is correct |
24 |
Correct |
21 ms |
28816 KB |
Output is correct |
25 |
Correct |
471 ms |
85360 KB |
Output is correct |
26 |
Correct |
83 ms |
39864 KB |
Output is correct |
27 |
Correct |
324 ms |
78212 KB |
Output is correct |
28 |
Correct |
439 ms |
82696 KB |
Output is correct |
29 |
Correct |
316 ms |
80320 KB |
Output is correct |
30 |
Correct |
318 ms |
78344 KB |
Output is correct |
31 |
Correct |
462 ms |
85296 KB |
Output is correct |
32 |
Correct |
365 ms |
78768 KB |
Output is correct |
33 |
Correct |
464 ms |
84480 KB |
Output is correct |
34 |
Correct |
15 ms |
28756 KB |
Output is correct |
35 |
Correct |
17 ms |
28756 KB |
Output is correct |
36 |
Correct |
16 ms |
28680 KB |
Output is correct |
37 |
Correct |
18 ms |
28628 KB |
Output is correct |
38 |
Correct |
18 ms |
28540 KB |
Output is correct |
39 |
Correct |
17 ms |
28740 KB |
Output is correct |
40 |
Correct |
20 ms |
28756 KB |
Output is correct |
41 |
Correct |
18 ms |
28796 KB |
Output is correct |
42 |
Correct |
15 ms |
28740 KB |
Output is correct |
43 |
Correct |
15 ms |
28756 KB |
Output is correct |
44 |
Correct |
15 ms |
28756 KB |
Output is correct |
45 |
Correct |
16 ms |
28756 KB |
Output is correct |
46 |
Correct |
15 ms |
28756 KB |
Output is correct |
47 |
Correct |
17 ms |
28772 KB |
Output is correct |
48 |
Correct |
14 ms |
28756 KB |
Output is correct |
49 |
Correct |
16 ms |
28880 KB |
Output is correct |
50 |
Correct |
16 ms |
28804 KB |
Output is correct |
51 |
Correct |
16 ms |
28728 KB |
Output is correct |
52 |
Correct |
17 ms |
28756 KB |
Output is correct |
53 |
Correct |
16 ms |
28740 KB |
Output is correct |
54 |
Correct |
16 ms |
28756 KB |
Output is correct |
55 |
Correct |
16 ms |
28756 KB |
Output is correct |
56 |
Correct |
18 ms |
28756 KB |
Output is correct |
57 |
Correct |
18 ms |
28756 KB |
Output is correct |
58 |
Correct |
392 ms |
77664 KB |
Output is correct |
59 |
Correct |
436 ms |
82956 KB |
Output is correct |
60 |
Correct |
359 ms |
72332 KB |
Output is correct |
61 |
Correct |
404 ms |
80548 KB |
Output is correct |
62 |
Correct |
80 ms |
40140 KB |
Output is correct |
63 |
Correct |
404 ms |
81256 KB |
Output is correct |
64 |
Correct |
325 ms |
78956 KB |
Output is correct |
65 |
Correct |
423 ms |
81756 KB |
Output is correct |
66 |
Correct |
435 ms |
84060 KB |
Output is correct |
67 |
Correct |
289 ms |
77108 KB |
Output is correct |
68 |
Correct |
422 ms |
83360 KB |
Output is correct |
69 |
Correct |
414 ms |
81672 KB |
Output is correct |
70 |
Correct |
284 ms |
77196 KB |
Output is correct |
71 |
Correct |
310 ms |
79692 KB |
Output is correct |
72 |
Correct |
304 ms |
78912 KB |
Output is correct |
73 |
Correct |
439 ms |
85148 KB |
Output is correct |
74 |
Correct |
296 ms |
78428 KB |
Output is correct |
75 |
Correct |
430 ms |
83784 KB |
Output is correct |
76 |
Correct |
461 ms |
84700 KB |
Output is correct |
77 |
Correct |
423 ms |
83068 KB |
Output is correct |
78 |
Correct |
306 ms |
78908 KB |
Output is correct |
79 |
Correct |
465 ms |
82588 KB |
Output is correct |
80 |
Correct |
350 ms |
79220 KB |
Output is correct |
81 |
Correct |
431 ms |
83564 KB |
Output is correct |