oj.uz

Submission #1048316

# Submission time Handle Problem Language Result Execution time Memory
1048316 2024-08-08T06:44:04 Z 정민찬(#11037) Make them Meet (EGOI24_makethemmeet) C++17
55.2677 / 100
 5 ms 1112 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 down[110];

void construct(int x) {
    if (g[x].empty()) return;
    vector<int> qry(N);
    for (auto &y : g[x]) {
        if (g[y].empty()) continue;
        iota(qry.begin(), qry.end(), 1);
        qry[x] = 0;
        qry[y] = 0;
        ans.push_back(qry);
        construct(y);
        ans.push_back(qry);
    }
    
    iota(qry.begin(), qry.end(), 1);
    qry[x] = 0;
    for (auto &y : g[x]) qry[y] = 0;
    ans.push_back(qry);
    if (g[x].size() > 1) {
        for (auto &y : g[x]) {
            iota(qry.begin(), qry.end(), 1);
            qry[x] = 0;
            qry[y] = 0;
            ans.push_back(qry);
            ans.push_back(qry);
        }
    }
    vector<int> t;
    for (auto &y : g[x]) {
        if (down[y] != -1) {
            t.push_back(y);
        }
    }
    if (t.empty()) {
        down[x] = g[x][0];
        iota(qry.begin(), qry.end(), 1);
        qry[x] = 0;
        qry[down[x]] = 0;
        ans.push_back(qry);
        return;
    }
    if (t.size() > 1) {
        iota(qry.begin(), qry.end(), 1);
        qry[x] = 0;
        qry[t[0]] = 0;
        ans.push_back(qry);
        for (int i=1; i<t.size(); i++) {
            iota(qry.begin(), qry.end(), 1);
            qry[t[i]] = 0;
            qry[down[t[i]]] = 0;
            ans.push_back(qry);
        }
        iota(qry.begin(), qry.end(), 1);
        qry[x] = 0;
        for (auto &y : t) qry[y] = 0;
        ans.push_back(qry);
        for (auto &y : t) {
            iota(qry.begin(), qry.end(), 1);
            qry[x] = 0;
            qry[y] = 0;
            ans.push_back(qry);
            ans.push_back(qry);
        }
    }
    iota(qry.begin(), qry.end(), 1);
    qry[x] = 0;
    qry[t[0]] = 0;
    qry[down[t[0]]] = 0;
    ans.push_back(qry);
    down[x] = t[0];
}

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);
    }
    make_tree(0);
    travel(0);
    memset(down, -1, sizeof(down));
    construct(0);
    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 construct(int)':
Main.cpp:83:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int i=1; i<t.size(); i++) {
      |                       ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     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 604 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB If people start at 1 and 2, then they can avoid each other
3 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 3 ms 816 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 604 KB Output is correct

Subtask #4
34.2676691712 / 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 604 KB Output is correct
6 Correct 1 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 3 ms 816 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 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 1 ms 348 KB Output is correct
21 Correct 3 ms 860 KB Output is correct
22 Correct 2 ms 860 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 Partially correct 3 ms 848 KB Partially correct
28 Partially correct 3 ms 856 KB Partially correct
29 Partially correct 3 ms 860 KB Partially correct
30 Partially correct 3 ms 856 KB Partially correct
31 Partially correct 3 ms 860 KB Partially correct
32 Partially correct 2 ms 860 KB Partially correct
33 Partially correct 3 ms 860 KB Partially correct
34 Partially correct 3 ms 860 KB Partially correct
35 Correct 5 ms 860 KB Output is correct
36 Correct 3 ms 604 KB Output is correct
37 Correct 2 ms 644 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 3 ms 856 KB Output is correct
40 Partially correct 3 ms 860 KB Partially correct
41 Partially correct 4 ms 860 KB Partially correct
42 Correct 2 ms 600 KB Output is correct
43 Correct 3 ms 1112 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Partially correct 2 ms 860 KB Partially 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 0 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 1 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 0 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 1 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 604 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB If people start at 1 and 2, then they can avoid each other
8 Halted 0 ms 0 KB -