CSES - HIIT Open 2024

Submission details
Task:	Light rail connections
Sender:	asdf4321
Submission time:	2024-11-16 16:53:43 +0200
Language:	C++ (C++17)
Status:	READY
Result:	WRONG ANSWER

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	WRONG ANSWER	0.06 s	details
#3	WRONG ANSWER	0.02 s	details
#4	ACCEPTED	0.00 s	details
#5	RUNTIME ERROR	0.00 s	details
#6	ACCEPTED	0.00 s	details
#7	RUNTIME ERROR	0.00 s	details
#8	ACCEPTED	0.01 s	details
#9	ACCEPTED	0.01 s	details
#10	RUNTIME ERROR	0.00 s	details
#11	ACCEPTED	0.40 s	details
#12	TIME LIMIT EXCEEDED	--	details
#13	RUNTIME ERROR	0.01 s	details
#14	ACCEPTED	0.25 s	details
#15	ACCEPTED	0.00 s	details
#16	RUNTIME ERROR	0.00 s	details
#17	RUNTIME ERROR	0.00 s	details
#18	RUNTIME ERROR	0.00 s	details
#19	ACCEPTED	0.00 s	details
#20	ACCEPTED	0.00 s	details
#21	ACCEPTED	0.00 s	details
#22	ACCEPTED	0.01 s	details
#23	ACCEPTED	0.01 s	details
#24	ACCEPTED	0.00 s	details
#25	ACCEPTED	0.00 s	details
#26	ACCEPTED	0.00 s	details
#27	ACCEPTED	0.01 s	details
#28	ACCEPTED	0.01 s	details
#29	ACCEPTED	0.00 s	details
#30	ACCEPTED	0.00 s	details
#31	ACCEPTED	0.00 s	details
#32	ACCEPTED	0.01 s	details
#33	ACCEPTED	0.01 s	details
#34	ACCEPTED	0.00 s	details
#35	ACCEPTED	0.00 s	details
#36	ACCEPTED	0.00 s	details
#37	ACCEPTED	0.00 s	details
#38	ACCEPTED	0.01 s	details

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 1001;

int n, m;
set<pii> es;
map<pii, pii> mp;

int par[N], sz[N];
int cc;

int fd (int u) {
    return par[u] == u ? u : par[u] = fd(par[u]);
}

bool unn (int u, int v) {
    u = fd(u), v = fd(v);
    if (u == v) return false;
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
    return true;
}

bool check(int uu, int vv) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    cc = n;

    for (auto [u, v] : es) {
        if (u == uu && v == vv) continue;
        if (unn(u, v)) cc--;
    }
    // cerr << cc << '\n';

    return cc == 1;
}

signed main() {
#ifdef LOCAL
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
#endif

    cin >> n >> m;

    vector<set<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        int uu = u, vv = v;
        if (u > v) swap(u, v);
        mp[{u, v}] = {uu, vv};
        es.insert({u, v});
        adj[u].insert(v);
        adj[v].insert(u);
    }

    int need = 3 * n;
    // need = 7;
    while (sz(es) > need) {
        for (int u = 0; u < n; u++) {
            if (sz(adj[u]) > 3) {
                // cerr << "mm " << u << '\n';
                int curdeg = sz(adj[u]);
                vector<int> will;
                for (int v : adj[u]) {
                    if (sz(adj[v]) == 2 || sz(adj[v]) > 3) {
                        will.push_back(v);
                    }
                }

                for (int v : will) {
                    if (curdeg == 3) break;
                    // cerr << u << ' ' << v << '\n';
                    int uu = u, vv = v;
                    if (uu > vv) swap(uu, vv);
                    // cerr << uu << ' ' << vv << ' ' << check(uu, vv) << '\n';
                    if (check(uu, vv)) {
                        curdeg--;
                        es.erase({uu, vv});
                        adj[uu].erase(vv);
                        adj[vv].erase(uu);
                    }
                }
            }
        }   
    }
    assert(check(-1, -1));

    cout << sz(es) << '\n';
    for (auto xx : es) {
        pii x = mp[xx];
        cout << x.first + 1 << ' ' << x.second + 1 << '\n';
    }
}

Test details

Test 1

Verdict: ACCEPTED

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

correct output
`8 1 2 1 3 1 4 2 3 ...` view save

user output
`8 1 2 1 3 1 4 2 3 ...` view save

Test 2

Verdict: WRONG ANSWER

input
`100 2451 1 2 1 3 1 4 1 5 ...` view save

correct output
`289 1 2 1 3 1 4 1 5 ...` view save

user output
`282 1 48 1 49 1 50 2 48 ...` view save

Test 3

Verdict: WRONG ANSWER

input
`100 1206 1 2 26 27 51 52 76 77 ...` view save

correct output
`282 1 2 1 3 1 4 1 5 ...` view save

user output
`260 1 25 1 51 1 76 2 23 ...` view save

Test 4

Verdict: ACCEPTED

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

correct output
`8 1 3 1 5 2 1 2 3 ...` view save

user output
`8 2 1 1 3 4 1 1 5 ...` view save

Test 5

Verdict: RUNTIME ERROR

input
`10 10 1 2 2 5 7 10 5 4 ...` view save

correct output
`10 1 2 1 6 2 5 2 10 ...` view save

user output
(empty)

Error:

code: input/code.cpp:101: int main(): Assertion `check(-1, -1)' failed.

Test 6

Verdict: ACCEPTED

input
`10 45 1 6 1 7 10 6 4 6 ...` view save

correct output
`27 1 3 1 6 1 7 1 9 ...` view save

user output
`21 1 8 1 9 10 1 2 8 ...` view save

Test 7

Verdict: RUNTIME ERROR

input
`100 45 42 4 39 75 99 87 9 65 ...` view save

correct output
`45 1 13 4 96 7 26 9 65 ...` view save

user output
(empty)

Error:

code: input/code.cpp:101: int main(): Assertion `check(-1, -1)' failed.

Test 8

Verdict: ACCEPTED

input
`100 400 19 66 48 11 34 85 22 9 ...` view save

correct output
`296 1 27 1 38 1 63 2 44 ...` view save

user output
`172 1 27 1 38 1 63 2 45 ...` view save

Test 9

Verdict: ACCEPTED

input
`100 500 17 75 80 65 89 16 65 73 ...` view save

correct output
`297 1 55 1 62 1 75 1 78 ...` view save

user output
`183 1 85 1 86 1 96 62 2 ...` view save

Test 10

Verdict: RUNTIME ERROR

input
`1000 500 989 549 7 137 716 180 20 265 ...` view save

correct output
`500 1 931 7 137 11 781 14 305 ...` view save

user output
(empty)

Error:

code: input/code.cpp:101: int main(): Assertion `check(-1, -1)' failed.

Test 11

Verdict: ACCEPTED

input
`1000 5000 911 615 730 255 283 617 821 101 ...` view save

correct output
`2992 1 359 1 579 1 688 1 826 ...` view save

user output
`1838 1 688 1 826 1 908 566 2 ...` view save

Test 12

Verdict: TIME LIMIT EXCEEDED

input
`1000 10000 116 615 301 287 869 274 717 549 ...` view save

correct output
`2997 1 165 1 496 1 661 2 22 ...` view save

user output
(empty)

Test 13

Verdict: RUNTIME ERROR

input
`1000 1000 395 816 73 640 124 192 920 419 ...` view save

correct output
`1000 2 903 3 634 4 959 5 274 ...` view save

user output
(empty)

Error:

code: input/code.cpp:101: int main(): Assertion `check(-1, -1)' failed.

Test 14

Verdict: ACCEPTED

input
`100 4000 18 66 63 12 50 12 48 78 ...` view save

correct output
`297 1 8 1 34 1 40 1 43 ...` view save

user output
`283 1 97 1 98 1 99 2 97 ...` view save

Test 15

Verdict: ACCEPTED

input
`1 0` view save

correct output
`0` view save

user output
`0` view save

Test 16

Verdict: RUNTIME ERROR

input
`10 0` view save

correct output
`0` view save

user output
(empty)

Error:

code: input/code.cpp:101: int main(): Assertion `check(-1, -1)' failed.

Test 17

Verdict: RUNTIME ERROR

input
`100 0` view save

correct output
`0` view save

user output
(empty)

Error:

code: input/code.cpp:101: int main(): Assertion `check(-1, -1)' failed.

Test 18

Verdict: RUNTIME ERROR

input
`1000 0` view save

correct output
`0` view save

user output
(empty)

Error:

code: input/code.cpp:101: int main(): Assertion `check(-1, -1)' failed.

Test 19

Verdict: ACCEPTED

input
`5 6 5 1 4 1 5 2 4 2 ...` view save

correct output
`6 4 1 4 2 4 3 5 1 ...` view save

user output
`6 4 1 5 1 4 2 5 2 ...` view save

Test 20

Verdict: ACCEPTED

input
`9 12 6 8 7 8 6 5 7 5 ...` view save

correct output
`12 6 2 6 5 6 8 7 1 ...` view save

user output
`12 7 1 9 1 6 2 7 2 ...` view save

Test 21

Verdict: ACCEPTED

input
`37 54 37 31 14 31 37 15 14 15 ...` view save

correct output
`54 6 2 6 7 6 19 6 30 ...` view save

user output
`54 20 1 26 1 6 2 28 2 ...` view save

Test 22

Verdict: ACCEPTED

input
`397 594 370 81 16 81 370 215 16 215 ...` view save

correct output
`594 4 19 4 31 4 60 4 110 ...` view save

user output
`594 208 1 342 1 7 2 247 2 ...` view save

Test 23

Verdict: ACCEPTED

input
`997 1494 555 594 295 594 555 422 295 422 ...` view save

correct output
`1494 6 214 6 280 6 455 6 472 ...` view save

user output
`1494 655 1 945 1 607 2 965 2 ...` view save

Test 24

Verdict: ACCEPTED

input
`6 8 5 3 6 3 5 4 6 4 ...` view save

correct output
`8 5 1 5 2 5 3 5 4 ...` view save

user output
`8 5 1 6 1 5 2 6 2 ...` view save

Test 25

Verdict: ACCEPTED

input
`11 16 6 5 11 5 6 3 11 3 ...` view save

correct output
`16 2 1 2 7 2 8 2 9 ...` view save

user output
`16 2 1 11 1 2 7 2 8 ...` view save

Test 26

Verdict: ACCEPTED

input
`46 72 20 46 33 46 20 15 33 15 ...` view save

correct output
`72 2 4 2 5 2 10 2 11 ...` view save

user output
`72 16 1 43 1 2 4 2 5 ...` view save

Test 27

Verdict: ACCEPTED

input
`496 792 129 244 128 244 129 230 128 230 ...` view save

correct output
`792 3 15 3 29 3 428 3 447 ...` view save

user output
`792 316 1 437 1 432 2 484 2 ...` view save

Test 28

Verdict: ACCEPTED

input
`996 1592 940 446 864 446 940 50 864 50 ...` view save

correct output
`1592 2 362 2 482 2 545 2 572 ...` view save

user output
`1592 531 1 614 1 2 362 2 482 ...` view save

Test 29

Verdict: ACCEPTED

input
`3 2 3 1 2 1` view save

correct output
`2 2 1 3 1` view save

user output
`2 2 1 3 1` view save

Test 30

Verdict: ACCEPTED

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

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

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

Test 31

Verdict: ACCEPTED

input
`19 18 5 2 1 2 1 4 15 4 ...` view save

correct output
`18 1 2 1 4 5 2 7 10 ...` view save

user output
`18 1 2 1 4 5 2 12 3 ...` view save

Test 32

Verdict: ACCEPTED

input
`199 198 20 93 53 93 53 7 152 7 ...` view save

correct output
`198 3 44 3 128 5 18 5 184 ...` view save

user output
`198 87 1 154 1 34 2 148 2 ...` view save

Test 33

Verdict: ACCEPTED

input
`999 998 481 471 242 471 242 95 525 95 ...` view save

correct output
`998 2 267 2 303 3 378 3 644 ...` view save

user output
`998 52 1 180 1 2 267 2 303 ...` view save

Test 34

Verdict: ACCEPTED

input
`4 4 2 4 1 4 2 3 1 3` view save

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

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

Test 35

Verdict: ACCEPTED

input
`7 8 2 7 4 7 2 5 4 5 ...` view save

correct output
`8 2 5 2 7 4 1 4 3 ...` view save

user output
`8 4 1 6 1 2 5 2 7 ...` view save

Test 36

Verdict: ACCEPTED

input
`28 36 22 9 24 9 22 5 24 5 ...` view save

correct output
`36 3 8 3 18 3 21 3 27 ...` view save

user output
`36 11 1 26 1 6 2 25 2 ...` view save

Test 37

Verdict: ACCEPTED

input
`298 396 293 290 133 290 293 228 133 228 ...` view save

correct output
`396 1 62 1 112 1 174 1 250 ...` view save

user output
`396 1 62 1 112 1 174 1 250 ...` view save

Test 38

Verdict: ACCEPTED

input
`1000 1332 949 882 156 882 949 515 156 515 ...` view save

correct output
`1332 2 508 2 774 2 885 2 921 ...` view save

user output
`1332 674 1 880 1 2 508 2 774 ...` view save

HIIT Open 2024

Light rail connections

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

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Tasks

Submissions (asdf4321)