oj.uz

Submission #1048430

# Submission time Handle Problem Language Result Execution time Memory
1048430 2024-08-08T07:32:55 Z 정민찬(#11037) Make them Meet (EGOI24_makethemmeet) C++17
13 / 100
 2 ms 600 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);
    }
}

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);
    }
    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';
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i=0; i<ans.size(); i++) {
      |                   ~^~~~~~~~~~~

Subtask #1
0.0 / 10.0

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

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 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 600 KB Output is correct

Subtask #3
0.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 Incorrect 0 ms 348 KB If people start at 0 and 2, then they can avoid each other
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 36.0

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

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 376 KB Output is correct
3 Incorrect 0 ms 348 KB If people start at 1 and 2, then they can avoid each other
4 Halted 0 ms 0 KB -