CSES - Datatähti 2024 loppu

Submission details
Task:	Polut
Sender:	vgtcross
Submission time:	2024-01-20 15:22:10 +0200
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	33
#2	ACCEPTED	33
#3	ACCEPTED	34

Test results
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` view save

correct output
`YES 1 2 1 1` view save

user output
`YES 1 2 1 1` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5 8 3 4 2 4 2 5 1 3 ...` view save

correct output
`YES 2 2 5 3 1 3 4` view save

user output
`YES 1 2 4 1 3 4 5` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 300 74 145 156 176 192 168 141 133 ...` view save

correct output
`YES 87 200 136 117 13 169 22 187 1...` view save

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 ...` view save

correct output
`YES 90 84 70 170 117 129 17 31 186...` view save

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 ...` view save

correct output
`YES 7 70 186 22 171 36 40 135 193 41 91 25 42 160 83 2 173 5...` view save

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 ...` view save

correct output
`YES 109 70 125 78 128 170 126 184 ...` view save

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 ...` view save

correct output
`NO` view save

user output
`NO` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 500 41 93 98 4 171 72 127 166 ...` view save

correct output
`YES 88 76 116 195 197 82 42 130 46...` view save

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 ...` view save

correct output
`YES 154 191 183 77 3 173 83 112 15...` view save

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 ...` view save

correct output
`YES 24 156 123 30 189 95 34 5 96 1...` view save

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 ...` view save

correct output
`YES 27 168 116 136 175 180 12 89 6...` view save

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 ...` view save

correct output
`YES 9236 3099 5585 9185 7222 9342 ...` view save

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 ...` view save

correct output
`YES 8734 5847 7473 5388 4872 4557 ...` view save

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 ...` view save

correct output
`YES 5204 3987 6388 4732 4403 7869 ...` view save

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 ...` view save

correct output
`NO` view save

user output
`NO` view save

Test 16

Group: 2, 3

Verdict: ACCEPTED

input
`10000 20000 8908 287 2525 6024 1851 844 72 6898 ...` view save

correct output
`YES 2487 3806 7839 4969 2661 4199 ...` view save

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 ...` view save

correct output
`YES 6340 5076 2779 1201 7053 1720 ...` view save

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 ...` view save

correct output
`YES 163946 182154 120966 26194 771...` view save

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 ...` view save

correct output
`YES 30833 112330 10351 23335 11682...` view save

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 ...` view save

correct output
`YES 99923 156477 12892 147937 1060...` view save

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 ...` view save

correct output
`NO` view save

user output
`NO` view save

Test 22

Group: 3

Verdict: ACCEPTED

input
`200000 500000 181062 44502 115318 176115 33437 57568 163325 17752 ...` view save

correct output
`YES 141551 129409 52010 108449 242...` view save

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 ...` view save

correct output
`YES 170843 113031 163271 166394 43...` view save

user output
`YES 170843 113031 163271 166394 43...` Truncated

Datatähti 2024 loppu

Polut

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Tasks

Submissions (vgtcross)