Submission #1161603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161603		Andrey	Make them Meet (EGOI24_makethemmeet)	C++20	100 / 100	6 ms	840 KiB

Main

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

vector<int> haha[1001];
vector<int> tree[1001];
vector<bool> bruh(1001,true);
vector<int> dep[1001];
vector<int> par(1001);
vector<pair<int,int>> troll(0);
vector<vector<int>> ans(0);

void dfs(int a, int t) {
    par[a] = t;
    if(t != -1) {
        troll.push_back({t,a});
    }
    for(int v: tree[a]) {
        dfs(v,a);
    }
    if(t != -1) {
        troll.push_back({t,a});
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m,a,b;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> a >> b;
        haha[a].push_back(b);
        haha[b].push_back(a);
    }
    if(m == n*(n-1)/2) {
        int ans[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                ans[i][j] = j;
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = i+1; j < n; j++) {
                ans[(i+j)%n][i] = ans[(i+j)%n][j];
            }
        }
        cout << 2*n << "\n";
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cout << ans[i][j] << " ";
            }
            cout << "\n";
            for(int j = 0; j < n; j++) {
                cout << ans[i][j] << " ";
            }
            cout << "\n";
        }
    }
    else {
        int r;
        for(int i = 0; i < n; i++) {
            if(haha[i].size() < n-1) {
                r = i;
                break;
            }
        }
        vector<int> idk(1,r);
        int y = 0;
        dep[0].push_back(r);
        bruh[r] = false;
        while(true) {
            vector<int> idk2(0);
            for(int u: idk) {
                for(int v: haha[u]) {
                    if(bruh[v]) {
                        idk2.push_back(v);
                        dep[y+1].push_back(v);
                        bruh[v] = false;
                        tree[u].push_back(v);
                    }
                }
            }
            if(idk2.empty()) {
                break;
            }
            idk = idk2;
            y++;
        }
        dfs(r,-1);
        for(int i = n-(n%2); i >= 2; i-=2) {
            vector<int> wut(n);
            for(int v: dep[i]) {
                for(int j = 0; j < n; j++) {
                    wut[j] = j;
                }
                wut[v] = par[par[v]];
                wut[par[v]] = par[par[v]];
                ans.push_back(wut);
                for(int j = 0; j < n; j++) {
                    wut[j] = j;
                }
                wut[par[v]] = par[par[v]];
                ans.push_back(wut);
            }
        }
        for(int i = 0; i < troll.size(); i++) {
            vector<int> wut(n);
            for(int j = 0; j < n; j++) {
                wut[j] = j;
            }
            wut[troll[i].first] = troll[i].second;
            ans.push_back(wut);
        }
        for(int i = ans.size()-troll.size()-1; i >= 0; i--) {
            ans.push_back(ans[i]);
        }
        for(int i = n-(n%2)+1; i >= 3; i-=2) {
            vector<int> wut(n);
            for(int v: dep[i]) {
                for(int j = 0; j < n; j++) {
                    wut[j] = j;
                }
                wut[v] = par[par[v]];
                wut[par[v]] = par[par[v]];
                ans.push_back(wut);
                for(int j = 0; j < n; j++) {
                    wut[j] = j;
                }
                wut[par[v]] = par[par[v]];
                ans.push_back(wut);
            }
        }
        int x = dep[2][0];
        for(int v: dep[1]) {
            if(v != x) {
                vector<int> wut(n);
                for(int j = 0; j < n; j++) {
                    wut[j] = j;
                }
                wut[x] = par[x];
                ans.push_back(wut);
                for(int j = 0; j < n; j++) {
                    wut[j] = j;
                }
                wut[v] = r;
                ans.push_back(wut);
                for(int j = 0; j < n; j++) {
                    wut[j] = j;
                }
                wut[par[x]] = r;
                wut[x] = r;
                ans.push_back(wut);
            }
        }
        vector<int> wut(n);
        for(int j = 0; j < n; j++) {
            wut[j] = j;
        }
        wut[par[x]] = r;
        cout << ans.size() << "\n";
        for(vector<int> wut: ans) {
            for(int i = 0; i < n; i++) {
                cout << wut[i] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 11 / 11
• Subtask 4: 36 / 36
• Subtask 5: 30 / 30