oj.uz

Submission #1048556

# Submission time Handle Problem Language Result Execution time Memory
1048556 2024-08-08T08:22:09 Z 정민찬(#11037) Make them Meet (EGOI24_makethemmeet) C++17
70 / 100
 3 ms 780 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

int N, M;
vector<int> adj[110];
vector<int> g[110];
int vis[110];

void make_tree(int x) {
    vis[x] = 1;
    for (auto &y : adj[x]) {
        if (vis[y]) continue;
        g[x].push_back(y);
        make_tree(y);
    }
}

vector<vector<int>> ans;

void travel(int x) {
    vector<int> qry(N);
    for (auto &y : g[x]) {
        iota(qry.begin(), qry.end(), 1);
        qry[x] = 0;
        qry[y] = 0;
        ans.push_back(qry);
        travel(y);
        ans.push_back(qry);
    }
}

int chk[110][110];

void complete() {
    int flag = 0;
    int n = N;
    if (N % 2 == 1) {
        make_tree(N-1);
        travel(N-1);
        flag = 1;
        n = N - 1;
    }
    while (true) {
        vector<int> C(n, 0);
        vector<pair<int,int>> v;
        for (int i=0; i<n; i++) {
            if (C[i]) continue;
            int pr = -1;
            for (int j=0; j<n; j++) {
                if (i == j) continue;
                if (!C[j] && !chk[i][j]) {
                    pr = j;
                    break;
                }
            }
            if (pr != -1) {
                v.push_back({i, pr});
                C[i] = 1;
                C[pr] = 1;
                chk[i][pr] = chk[pr][i] = 1;
            }
        }
        if (v.empty()) break;
        int p = -1;
        for (int i=0; i<n; i++) {
            if (!C[i]) {
                if (p != -1) {
                    v.push_back({i, p});
                    p = -1;
                }
                else p = i;
            }
        }
        vector<int> qry(N);
        for (int i=0; i<n/2; i++) {
            qry[v[i].first] = i;
            qry[v[i].second] = i;
        }
        if (flag) qry.back() = n/2;
        ans.push_back(qry);
        ans.push_back(qry);
    }
}

vector<int> vtx;
vector<int> qry;

void init() {
    iota(qry.begin(), qry.end(), 0);
}

void grp(vector<int> v) {
    for (int i=1; i<v.size(); i++) {
        qry[v[i]] = v[0];
    }
}

void Push() {
    ans.push_back(qry);
}

void construct(int a, int b, int c, int x) {
    vtx.push_back(x);
    if (vtx.size() % 2 == 0) {
        init();
        for (int i=0; i<vtx.size(); i+=2) {
            grp({vtx[i], vtx[i+1]});
        }
        Push();
    }
    else {
        init();
        grp({a, b, c});
        for (int i=3; i<vtx.size(); i+=2) {
            grp({vtx[i], vtx[i+1]});
        }
        Push();
    }
    for (auto &y : g[x]) {
        construct(a, b, c, y);
        if (vtx.size() % 2 == 0) {
            init();
            for (int i=0; i<vtx.size(); i+=2) {
                grp({vtx[i], vtx[i+1]});
            }
            Push();
        }
        else {
            init();
            grp({a, b, c});
            for (int i=3; i<vtx.size(); i+=2) {
                grp({vtx[i], vtx[i+1]});
            }
            Push();
        }
    }
    vtx.pop_back();
}

int exi[110][110];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> M;
    for (int i=0; i<M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        exi[u][v] = exi[v][u] = 1;
    }
    if (M == N * (N-1) / 2) {
        complete();
        cout << ans.size() << '\n';
        for (int i=0; i<ans.size(); i++) {
            for (int j=0; j<N; j++) {
                cout << ans[i][j] << ' ';
            }
            cout << '\n';
        }
        return 0;
    }
    int a = -1, b, c;
    bool flag = false;
    for (int i=0; i<N; i++) {
        for (auto &j : adj[i]) {
            for (auto &k : adj[i]) {
                if (j != k && !chk[j][k]) {
                    a = j;
                    b = i;
                    c = k;
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        if (flag) break;
    }
    assert(flag);
    vis[a] = vis[b] = vis[c] = 1;
    g[b].push_back(a);
    g[b].push_back(c);
    make_tree(c);
    make_tree(a);
    make_tree(b);
    int cnt = 0;
    for (int i=0; i<N; i++) {
        cnt += g[i].size();
    }
    assert(cnt == N-1);
    travel(b);
    qry.resize(N);
    vtx = {a, b};
    construct(a, b, c, c);
    init();
    grp({b, c});
    Push();
    vtx = {c, b};
    construct(c, b, a, a);
    for (auto &y : g[b]) {
        if (y == c || y == a) continue;
        assert(!chk[y][c] && !chk[y][a]);
        init();
        grp({b, c});
        Push();
        vtx = {c, b};
        construct(c, b, y, y);
    }
    cout << ans.size() << '\n';
    for (int i=0; i<ans.size(); i++) {
        for (int j=0; j<N; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }
}

Compilation message

Main.cpp: In function 'void grp(std::vector<int>)':
Main.cpp:97:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i=1; i<v.size(); i++) {
      |                   ~^~~~~~~~~
Main.cpp: In function 'void construct(int, int, int, int)':
Main.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for (int i=0; i<vtx.size(); i+=2) {
      |                       ~^~~~~~~~~~~
Main.cpp:118:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for (int i=3; i<vtx.size(); i+=2) {
      |                       ~^~~~~~~~~~~
Main.cpp:127:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             for (int i=0; i<vtx.size(); i+=2) {
      |                           ~^~~~~~~~~~~
Main.cpp:135:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |             for (int i=3; i<vtx.size(); i+=2) {
      |                           ~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:159:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         for (int i=0; i<ans.size(); i++) {
      |                       ~^~~~~~~~~~~
Main.cpp:215:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |     for (int i=0; i<ans.size(); i++) {
      |                   ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
36.0 / 36.0

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

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 732 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 2 ms 600 KB Output is correct
31 Correct 2 ms 700 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 0 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 2 ms 604 KB Output is correct
37 Correct 2 ms 604 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 2 ms 604 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 2 ms 604 KB Output is correct
43 Correct 2 ms 744 KB Output is correct
44 Correct 3 ms 604 KB Output is correct
45 Correct 2 ms 604 KB Output is correct
46 Correct 2 ms 604 KB Output is correct
47 Correct 2 ms 716 KB Output is correct
48 Correct 2 ms 604 KB Output is correct
49 Correct 2 ms 604 KB Output is correct
50 Correct 2 ms 604 KB Output is correct
51 Correct 2 ms 604 KB Output is correct
52 Correct 2 ms 604 KB Output is correct
53 Correct 2 ms 600 KB Output is correct
54 Correct 2 ms 604 KB Output is correct
55 Correct 0 ms 348 KB Output is correct
56 Correct 0 ms 348 KB Output is correct
57 Correct 0 ms 348 KB Output is correct
58 Correct 0 ms 348 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 1 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 0 ms 348 KB Output is correct
63 Correct 0 ms 348 KB Output is correct
64 Correct 0 ms 348 KB Output is correct
65 Correct 0 ms 348 KB Output is correct
66 Correct 0 ms 348 KB Output is correct
67 Correct 0 ms 348 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 1 ms 348 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 0 ms 348 KB Output is correct
75 Correct 0 ms 348 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 0 ms 348 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 344 KB Output is correct
81 Correct 0 ms 348 KB Output is correct
82 Correct 0 ms 348 KB Output is correct
83 Correct 0 ms 348 KB Output is correct
84 Correct 0 ms 348 KB Output is correct
85 Correct 1 ms 348 KB Output is correct
86 Correct 1 ms 348 KB Output is correct
87 Correct 2 ms 604 KB Output is correct
88 Correct 0 ms 348 KB Output is correct
89 Correct 0 ms 348 KB Output is correct
90 Correct 1 ms 348 KB Output is correct
91 Correct 2 ms 604 KB Output is correct
92 Correct 2 ms 600 KB Output is correct
93 Correct 1 ms 604 KB Output is correct
94 Correct 0 ms 348 KB Output is correct
95 Correct 0 ms 348 KB Output is correct
96 Correct 0 ms 348 KB Output is correct
97 Correct 2 ms 600 KB Output is correct
98 Correct 2 ms 712 KB Output is correct
99 Correct 2 ms 604 KB Output is correct
100 Correct 2 ms 604 KB Output is correct
101 Correct 3 ms 780 KB Output is correct
102 Correct 3 ms 604 KB Output is correct
103 Correct 2 ms 608 KB Output is correct
104 Correct 2 ms 616 KB Output is correct
105 Correct 2 ms 608 KB Output is correct
106 Correct 2 ms 616 KB Output is correct
107 Correct 2 ms 616 KB Output is correct
108 Correct 2 ms 732 KB Output is correct
109 Correct 2 ms 600 KB Output is correct
110 Correct 2 ms 604 KB Output is correct
111 Correct 2 ms 604 KB Output is correct
112 Correct 2 ms 604 KB Output is correct
113 Correct 2 ms 604 KB Output is correct
114 Correct 2 ms 604 KB Output is correct
115 Correct 2 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 0 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 0 ms 348 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 0 ms 348 KB Output is correct
127 Correct 0 ms 348 KB Output is correct
128 Correct 0 ms 344 KB Output is correct
129 Correct 0 ms 348 KB Output is correct
130 Correct 0 ms 348 KB Output is correct
131 Correct 0 ms 348 KB Output is correct
132 Correct 1 ms 348 KB Output is correct
133 Correct 0 ms 348 KB Output is correct
134 Correct 0 ms 348 KB Output is correct
135 Correct 0 ms 348 KB Output is correct
136 Correct 0 ms 348 KB Output is correct
137 Incorrect 0 ms 348 KB If people start at 1 and 2, then they can avoid each other
138 Halted 0 ms 0 KB -