Task: | Polut |
Sender: | vgtcross |
Submission time: | 2024-01-20 15:22:10 +0200 |
Language: | C++20 |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 33 |
#2 | ACCEPTED | 33 |
#3 | ACCEPTED | 34 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#12 | ACCEPTED | 0.02 s | 2, 3 | details |
#13 | ACCEPTED | 0.02 s | 2, 3 | details |
#14 | ACCEPTED | 0.02 s | 2, 3 | details |
#15 | ACCEPTED | 0.02 s | 2, 3 | details |
#16 | ACCEPTED | 0.03 s | 2, 3 | details |
#17 | ACCEPTED | 0.03 s | 2, 3 | details |
#18 | ACCEPTED | 0.34 s | 3 | details |
#19 | ACCEPTED | 0.46 s | 3 | details |
#20 | ACCEPTED | 0.53 s | 3 | details |
#21 | ACCEPTED | 0.47 s | 3 | details |
#22 | ACCEPTED | 0.77 s | 3 | details |
#23 | ACCEPTED | 0.81 s | 3 | details |
Compiler report
input/code.cpp: In function 'void solve()': input/code.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare] 88 | while (j < evt.size() && evt[j].fi == i) { | ~~^~~~~~~~~~~~
Code
#include <bits/stdc++.h> #define all(x) begin(x),end(x) #define fi first #define se second using namespace std; using ll = long long; using pic = pair<int, char>; using pii = pair<int, int>; const int N = 200200; vector<int> adj[N], rev[N]; set<int> cur; set<int> nx; vector<int> ord; bool vis[N]; void dfs(int u) { if (vis[u]) return; vis[u] = 1; for (int v : adj[u]) dfs(v); ord.push_back(u); } void solve() { int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); rev[v].push_back(u); } for (int i = 1; i <= n; ++i) { rev[i].push_back(0); rev[i].push_back(-1); } for (int i = 1; i <= n; ++i) dfs(i); reverse(all(ord)); for (int i = 1; i <= n; ++i) nx.insert(i); cur.insert(0); cur.insert(-1); vector<pii> evt; for (int i = 1; i < n; ++i) { int u = ord[i-1]; int v = ord[i]; set<int> ins; bool insu = 0; if (nx.count(v)) { insu = 1; for (int w : adj[u]) ins.insert(w); } if (!count(all(adj[u]), v)) { nx.clear(); for (int j : cur) evt.push_back({i, j}); cur.clear(); } if (insu) cur.insert(u); for (int i : ins) nx.insert(i); if (cur.empty()) { cout << "NO\n"; return; } } reverse(all(evt)); vector<int> p, q; int a = ord[n-1]; int i = n-1, j = 0; while (i >= 0) { swap(p, q); if (q.empty()) a = *cur.begin(); else { for (int j : rev[q.back()]) if (cur.count(j)) { a = j; break; } } cur.erase(a); assert(a != ord[i]); while (i >= 0 && ord[i] != a) { p.push_back(ord[i]); while (j < evt.size() && evt[j].fi == i) { cur.insert(evt[j].se); ++j; } --i; } } reverse(all(p)); reverse(all(q)); cout << "YES\n"; cout << p.size() << ' '; for (int i : p) cout << i << ' '; cout << '\n'; cout << q.size() << ' '; for (int i : q) cout << i << ' '; cout << '\n'; } int main() { cin.tie(0) -> sync_with_stdio(0); solve(); return 0; }
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 0 |
correct output |
---|
YES 1 2 1 1 |
user output |
---|
YES 1 2 1 1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
5 8 3 4 2 4 2 5 1 3 ... |
correct output |
---|
YES 2 2 5 3 1 3 4 |
user output |
---|
YES 1 2 4 1 3 4 5 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
200 300 74 145 156 176 192 168 141 133 ... |
correct output |
---|
YES 87 200 136 117 13 169 22 187 1... |
user output |
---|
YES 87 200 136 117 13 169 22 187 1... Truncated |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
200 500 37 119 47 10 17 31 130 28 ... |
correct output |
---|
YES 90 84 70 170 117 129 17 31 186... |
user output |
---|
YES 90 84 70 170 117 129 17 31 186... Truncated |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
200 500 79 1 104 127 31 38 83 85 ... |
correct output |
---|
YES 7 70 186 22 171 36 40 135 193 41 91 25 42 160 83 2 173 5... |
user output |
---|
YES 7 70 186 22 171 36 40 135 193 41 91 25 42 160 83 2 173 5... Truncated |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
200 500 145 50 4 102 136 55 148 34 ... |
correct output |
---|
YES 109 70 125 78 128 170 126 184 ... |
user output |
---|
YES 114 70 125 78 128 5 126 100 11... Truncated |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
200 500 44 38 198 85 69 167 74 39 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
200 500 41 93 98 4 171 72 127 166 ... |
correct output |
---|
YES 88 76 116 195 197 82 42 130 46... |
user output |
---|
YES 163 58 136 178 152 128 160 14 ... Truncated |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
192 494 17 148 82 57 100 152 38 102 ... |
correct output |
---|
YES 154 191 183 77 3 173 83 112 15... |
user output |
---|
YES 154 191 183 77 3 173 83 112 15... Truncated |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
193 497 24 110 17 193 129 117 23 186 ... |
correct output |
---|
YES 24 156 123 30 189 95 34 5 96 1... |
user output |
---|
YES 24 156 123 30 189 95 34 5 96 1... Truncated |
Test 11
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
194 500 57 158 23 40 31 50 189 121 ... |
correct output |
---|
YES 27 168 116 136 175 180 12 89 6... |
user output |
---|
YES 27 168 116 136 175 180 12 89 6... Truncated |
Test 12
Group: 2, 3
Verdict: ACCEPTED
input |
---|
10000 15000 8243 3033 3299 579 4920 2342 2816 7811 ... |
correct output |
---|
YES 9236 3099 5585 9185 7222 9342 ... |
user output |
---|
YES 9236 3099 5585 9185 7222 9342 ... Truncated |
Test 13
Group: 2, 3
Verdict: ACCEPTED
input |
---|
10000 20000 6246 3603 5105 3531 6953 4682 2625 3510 ... |
correct output |
---|
YES 8734 5847 7473 5388 4872 4557 ... |
user output |
---|
YES 8734 5847 7473 5388 4872 4557 ... Truncated |
Test 14
Group: 2, 3
Verdict: ACCEPTED
input |
---|
10000 20000 5853 1019 2465 2936 2022 3609 9429 4118 ... |
correct output |
---|
YES 5204 3987 6388 4732 4403 7869 ... |
user output |
---|
YES 4884 3987 6388 4732 4403 7869 ... Truncated |
Test 15
Group: 2, 3
Verdict: ACCEPTED
input |
---|
10000 20000 3439 3806 9336 5210 7784 848 5162 9830 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 16
Group: 2, 3
Verdict: ACCEPTED
input |
---|
10000 20000 8908 287 2525 6024 1851 844 72 6898 ... |
correct output |
---|
YES 2487 3806 7839 4969 2661 4199 ... |
user output |
---|
YES 4253 5543 7582 4661 4165 5389 ... Truncated |
Test 17
Group: 2, 3
Verdict: ACCEPTED
input |
---|
7621 19995 6223 473 4893 990 5326 3614 421 591 ... |
correct output |
---|
YES 6340 5076 2779 1201 7053 1720 ... |
user output |
---|
YES 6340 5076 2779 1201 7053 1720 ... Truncated |
Test 18
Group: 3
Verdict: ACCEPTED
input |
---|
200000 300000 17151 175317 68698 43101 190738 54240 105443 37722 ... |
correct output |
---|
YES 163946 182154 120966 26194 771... |
user output |
---|
YES 163946 182154 120966 26194 771... Truncated |
Test 19
Group: 3
Verdict: ACCEPTED
input |
---|
200000 500000 128290 197429 67543 48696 156347 40114 114481 197 ... |
correct output |
---|
YES 30833 112330 10351 23335 11682... |
user output |
---|
YES 30833 112330 10351 23335 11682... Truncated |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
200000 500000 93623 55553 60858 72598 15531 30650 196624 28459 ... |
correct output |
---|
YES 99923 156477 12892 147937 1060... |
user output |
---|
YES 100116 156477 12892 147937 106... Truncated |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
200000 500000 76457 8199 163450 19462 107840 24269 178642 128924 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 22
Group: 3
Verdict: ACCEPTED
input |
---|
200000 500000 181062 44502 115318 176115 33437 57568 163325 17752 ... |
correct output |
---|
YES 141551 129409 52010 108449 242... |
user output |
---|
YES 83713 47477 92161 198598 15236... Truncated |
Test 23
Group: 3
Verdict: ACCEPTED
input |
---|
190479 499998 113031 136485 5993 50604 19834 84581 39043 93744 ... |
correct output |
---|
YES 170843 113031 163271 166394 43... |
user output |
---|
YES 170843 113031 163271 166394 43... Truncated |