oj.uz

Submission #1098572

# Submission time Handle Problem Language Result Execution time Memory
1098572 2024-10-09T15:38:11 Z Trisanu_Das Make them Meet (EGOI24_makethemmeet) C++17
70 / 100
 1874 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    vector<vector<int>> adj(n, vector<int>(n, 0));
    
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        if (x == y || adj[x][y]) continue;
        g[x].push_back(y);
        g[y].push_back(x);
        adj[x][y] = adj[y][x] = 1;
    }

    if (!count_if(g.begin(), g.end(), [&](const vector<int>& v) { return v.size() < n - 1; })) {
        int q = n + (n % 2);
        vector<int> circ(q), col(q, 0);
        iota(circ.begin(), circ.end(), 0);
        cout << 2 * (q - 1) << endl;
        for (int _ = 0; _ < q - 1; _++) {
            for (int i = 0; i < q / 2; i++) {
                col[circ[i]] = col[circ[q - 1 - i]] = i;
            }
            for (int i = 0; i < n; i++) cout << col[i] << ' ';
            cout << endl;
            for (int i = 0; i < n; i++) cout << col[i] << ' ';
            cout << endl;
            rotate(circ.begin() + 1, circ.begin() + 2, circ.end());
        }
        return 0;
    }

    auto go = [&]() {
        for (int r = 0; r < n; r++) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < n; y++) {
                    if (r != x && r != y && x != y) {
                        if (adj[r][x] == 1 && adj[r][y] == 1 && adj[x][y] == 0) {
                            g[r].insert(g[r].begin(), {x, y});
                            return r;
                        }
                    }
                }
            }
        }
        return -1;
    };

    int root = go();
    assert(root != -1);

    vector<vector<int>> childs(n);
    vector<int> par(n, -1);
    par[root] = -2;
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int y : g[x]) {
            if (par[y] == -1) {
                childs[x].push_back(y);
                par[y] = x;
                q.push(y);
            }
        }
    }

    for (int x : childs[root]) {
        vector<int> bad;
        for (int y : childs[root]) {
            if (adj[x][y]) bad.push_back(y);
        }
        for (int y : bad) {
            childs[root].erase(remove(childs[root].begin(), childs[root].end(), y), childs[root].end());
            childs[x].push_back(y);
            par[y] = x;
        }
    }

    vector<vector<int>> ans;
    vector<int> free(n, 0);
    free[root] = 1;
    
    while (accumulate(free.begin(), free.end(), 0) < n - 1) {
        vector<int> col(n), active(free), nfree(free);
        iota(col.begin(), col.end(), 1);

        if (!free[root]) {
            int best = 1e9, b = -1;
            for (int x : childs[root]) {
                int pending = count_if(childs[x].begin(), childs[x].end(), [&](int y) { return !free[y]; });
                if (free[x] && pending < best) {
                    best = pending;
                    b = x;
                }
            }
            active[b] = 0;
            col[b] = col[root];
            nfree[b] = 0;
            nfree[root] = 1;
        } else {
            active[root] = 1e9;
        }

        for (int x = 0; x < n; x++) {
            if (x != root && !free[x] && active[par[x]] >= 1) {
                col[x] = col[par[x]];
                active[par[x]]--;
                nfree[x] = 1;
                nfree[par[x]] = 0;
            }
        }

        ans.push_back(col);
        free = nfree;
    }

    assert(!free[root]);

    function<void(int)> dfs = [&](int x) {
        for (int y : childs[x]) {
            vector<int> col(n);
            iota(col.begin(), col.end(), 1);
            col[y] = col[x];
            ans.push_back(col);
            dfs(y);
            ans.push_back(col);
        }
    };
    
    dfs(root);

    cout << ans.size() << endl;
    for (const auto& col : ans) {
        for (int c : col) cout << c << ' ';
        cout << endl;
    }

    return 0;
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:20:83: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     if (!count_if(g.begin(), g.end(), [&](const vector<int>& v) { return v.size() < n - 1; })) {
      |                                                                          ~~~~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 4 ms 468 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 2 ms 600 KB Output is correct

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 452 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 4 ms 604 KB Output is correct
22 Correct 3 ms 600 KB Output is correct
23 Correct 2 ms 600 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 3 ms 600 KB Output is correct
28 Correct 4 ms 600 KB Output is correct
29 Correct 3 ms 604 KB Output is correct
30 Correct 3 ms 604 KB Output is correct
31 Correct 3 ms 604 KB Output is correct
32 Correct 2 ms 712 KB Output is correct
33 Correct 3 ms 604 KB Output is correct
34 Correct 3 ms 604 KB Output is correct
35 Correct 5 ms 604 KB Output is correct
36 Correct 4 ms 604 KB Output is correct
37 Correct 3 ms 604 KB Output is correct
38 Correct 3 ms 604 KB Output is correct
39 Correct 4 ms 604 KB Output is correct
40 Correct 3 ms 604 KB Output is correct
41 Correct 3 ms 604 KB Output is correct
42 Correct 3 ms 604 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 3 ms 600 KB Output is correct
45 Correct 3 ms 604 KB Output is correct
46 Correct 1 ms 356 KB Output is correct
47 Correct 1 ms 344 KB Output is correct
48 Correct 1 ms 600 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 1 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 1 ms 348 KB Output is correct
57 Correct 1 ms 348 KB Output is correct
58 Correct 1 ms 348 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 1 ms 344 KB Output is correct
63 Correct 1 ms 344 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 1 ms 348 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 3 ms 724 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 452 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 3 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 4 ms 604 KB Output is correct
31 Correct 3 ms 600 KB Output is correct
32 Correct 2 ms 600 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 3 ms 600 KB Output is correct
37 Correct 4 ms 600 KB Output is correct
38 Correct 3 ms 604 KB Output is correct
39 Correct 3 ms 604 KB Output is correct
40 Correct 3 ms 604 KB Output is correct
41 Correct 2 ms 712 KB Output is correct
42 Correct 3 ms 604 KB Output is correct
43 Correct 3 ms 604 KB Output is correct
44 Correct 5 ms 604 KB Output is correct
45 Correct 4 ms 604 KB Output is correct
46 Correct 3 ms 604 KB Output is correct
47 Correct 3 ms 604 KB Output is correct
48 Correct 4 ms 604 KB Output is correct
49 Correct 3 ms 604 KB Output is correct
50 Correct 3 ms 604 KB Output is correct
51 Correct 3 ms 604 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 3 ms 600 KB Output is correct
54 Correct 3 ms 604 KB Output is correct
55 Correct 1 ms 356 KB Output is correct
56 Correct 1 ms 344 KB Output is correct
57 Correct 1 ms 600 KB Output is correct
58 Correct 1 ms 348 KB Output is correct
59 Correct 1 ms 348 KB Output is correct
60 Correct 1 ms 348 KB Output is correct
61 Correct 1 ms 348 KB Output is correct
62 Correct 1 ms 348 KB Output is correct
63 Correct 1 ms 344 KB Output is correct
64 Correct 1 ms 348 KB Output is correct
65 Correct 1 ms 348 KB Output is correct
66 Correct 1 ms 348 KB Output is correct
67 Correct 1 ms 348 KB Output is correct
68 Correct 1 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 1 ms 348 KB Output is correct
71 Correct 1 ms 344 KB Output is correct
72 Correct 1 ms 344 KB Output is correct
73 Correct 1 ms 348 KB Output is correct
74 Correct 1 ms 348 KB Output is correct
75 Correct 1 ms 348 KB Output is correct
76 Correct 1 ms 348 KB Output is correct
77 Correct 1 ms 344 KB Output is correct
78 Correct 2 ms 604 KB Output is correct
79 Correct 2 ms 604 KB Output is correct
80 Correct 0 ms 348 KB Output is correct
81 Correct 1 ms 348 KB Output is correct
82 Correct 0 ms 348 KB Output is correct
83 Correct 1 ms 348 KB Output is correct
84 Correct 1 ms 344 KB Output is correct
85 Correct 1 ms 348 KB Output is correct
86 Correct 1 ms 344 KB Output is correct
87 Correct 3 ms 600 KB Output is correct
88 Correct 1 ms 348 KB Output is correct
89 Correct 1 ms 344 KB Output is correct
90 Correct 2 ms 348 KB Output is correct
91 Correct 3 ms 604 KB Output is correct
92 Correct 3 ms 600 KB Output is correct
93 Correct 2 ms 604 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 1 ms 348 KB Output is correct
96 Correct 1 ms 348 KB Output is correct
97 Correct 3 ms 612 KB Output is correct
98 Correct 3 ms 604 KB Output is correct
99 Correct 3 ms 604 KB Output is correct
100 Correct 3 ms 604 KB Output is correct
101 Correct 4 ms 604 KB Output is correct
102 Correct 3 ms 604 KB Output is correct
103 Correct 3 ms 604 KB Output is correct
104 Correct 4 ms 656 KB Output is correct
105 Correct 3 ms 604 KB Output is correct
106 Correct 3 ms 708 KB Output is correct
107 Correct 4 ms 684 KB Output is correct
108 Correct 3 ms 600 KB Output is correct
109 Correct 3 ms 600 KB Output is correct
110 Correct 5 ms 604 KB Output is correct
111 Correct 3 ms 604 KB Output is correct
112 Correct 4 ms 604 KB Output is correct
113 Correct 3 ms 600 KB Output is correct
114 Correct 3 ms 600 KB Output is correct
115 Correct 3 ms 604 KB Output is correct
116 Correct 1 ms 348 KB Output is correct
117 Correct 0 ms 348 KB Output is correct
118 Correct 1 ms 348 KB Output is correct
119 Correct 1 ms 348 KB Output is correct
120 Correct 0 ms 348 KB Output is correct
121 Correct 0 ms 348 KB Output is correct
122 Correct 1 ms 344 KB Output is correct
123 Correct 0 ms 348 KB Output is correct
124 Correct 0 ms 348 KB Output is correct
125 Correct 0 ms 348 KB Output is correct
126 Correct 1 ms 348 KB Output is correct
127 Correct 1 ms 344 KB Output is correct
128 Correct 1 ms 348 KB Output is correct
129 Correct 1 ms 344 KB Output is correct
130 Correct 1 ms 344 KB Output is correct
131 Correct 1 ms 348 KB Output is correct
132 Correct 0 ms 348 KB Output is correct
133 Correct 1 ms 348 KB Output is correct
134 Correct 1 ms 348 KB Output is correct
135 Correct 1 ms 348 KB Output is correct
136 Runtime error 1874 ms 1048576 KB Execution killed with signal 9
137 Halted 0 ms 0 KB -