Submission #1250600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250600		LaMatematica14	Make them Meet (EGOI24_makethemmeet)	C++20	100 / 100	5 ms	584 KiB

Main

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

void sol_riga(int N, vector<int> &ord) {
    cout << 2*((N+1)/2) << "\n";
    for (int i = 0; i < (N+1)/2; i++) {
        vector<int> col(N);
        for (int j = 0; j < N; j+=2) {
            col[ord[j]] = ord[j];
            if (j+1 < N) col[ord[j+1]] = ord[j];
        }
        for (int j = 0; j < N; j++) cout << col[j] << " ";
        cout << "\n";
        col[ord[0]] = ord[0];
        for (int j = 1; j < N; j+=2) {
            col[ord[j]] = ord[j];
            if (j+1 < N) col[ord[j+1]] = ord[j];
        }
        for (int j = 0; j < N; j++) cout << col[j] << " ";
        cout << "\n";
    }
}

struct sol_albero {
    int N;
    vector<vector<int>> adj;
    vector<int> dist; //distanza di ogni nodo dalla radice
    vector<int> pad; //padre di ogni nodo
    
    void dfs(int att) {
        for (int pros : adj[att]){
            if (pros == pad[att]) continue;
            dist[pros] = dist[att]+1;
            pad[pros] = att;
            dfs(pros);
        }
    }
    
    void risolvi(int n, vector<vector<int>> aa, int rad, int pb, int aus) {
        N = n;
        adj.resize(N); dist.resize(N); pad.resize(N);
        fill(pad.begin(), pad.end(), -1); fill(dist.begin(), dist.end(), 0);
        for (int i = 0; i < N; i++) {
            adj[i] = aa[i];
        }
        cout << 6*N << "\n";
        dfs(rad);
        for (int k = 0; k < 2*N; k++) {
            for (int i = 0; i < N; i++) {
                if ((dist[i]%2) == 0|| i == pb) cout << i << " ";
                else cout << pad[i] << " ";
            }
            cout << "\n";
            for (int i = 0; i < N; i++) {
                if ((dist[i]%2) == 1) cout << i << " ";
                else if (i == rad) cout << aus << " ";
                else cout << pad[i] << " ";
            }
            cout << "\n";
            for (int i = 0; i < N; i++) {
                if (i == rad || i == pb) cout << rad << " ";
                else cout << i << " ";
            }
            cout << "\n";
        }
    }

};

int main() {
    //freopen("output.txt", "w", stdout);
    int N, M; cin >> N >> M;
    //cout << N << " " << M << "\n";
    vector<vector<int>> adj(N);
    vector<vector<bool>> mata(N, vector<bool> (N, 0));
    for (int i = 0; i < M; i++) {
        int a, b; cin >> a >> b;
        //cout << a << " " << b << "\n";
        adj[a].push_back(b);
        adj[b].push_back(a);
        mata[a][b] = 1; mata[b][a] = 1;
    }
    vector<int> pdr(N, -1);
    vector<bool> vis(N, 0);
    vector<int> prof(N, 0);
    vector<vector<int>> sptr(N);
    stack<int> dfs; dfs.push(0);
    while (!dfs.empty()) {
        int x = dfs.top(); dfs.pop();
        if (vis[x]) continue;
        vis[x] = 1;
        if(pdr[x] != -1) {
            prof[x] = prof[pdr[x]]+1;
            sptr[pdr[x]].push_back(x);
            sptr[x].push_back(pdr[x]);
        }
        for (int y : adj[x]) {
            if (vis[y]) continue;
            pdr[y] = x;
            dfs.push(y);
        }
    }

    fill(vis.begin(), vis.end(), 0);
    bool linea = 1; int beg;
    for (int i = 0; i < N; i++) {
        if (sptr[i].size() > 2) linea  = 0;
        if (sptr[i].size() == 1) beg = i;
    }
    if (linea) {
        vector<int> ord;
        ord.push_back(beg); vis[beg] = 1;
        do {
            if (vis[sptr[beg][0]]) beg = sptr[beg][1];
            else beg = sptr[beg][0];
            ord.push_back(beg); vis[beg] = 1;
        } while (sptr[beg].size() == 2);
        sol_riga(N, ord);
        return 0;
    }
    
    pair<int, int> gb = {0, 0};
    for (int i = 0; i < N; i++) {
        if (sptr[i].size() <= 2) continue;
        gb = max(gb, {prof[i], i});
    }
    vector<int> rs;
    bool pa = 1; int fp;
    for (int x : sptr[gb.second]) {
        if (x == pdr[gb.second]) continue;
        if (mata[x][pdr[gb.second]] || !pa) {
            rs.push_back(x);
            continue;
        }
        fp = x; pa = 0;
    }
    if (pa) {
        fp = rs[rs.size()-1];
        rs.pop_back();
    }

    //scendo sul ramo di fp per mantenerlo una linea
    vis[gb.second] = 1;
    vis[fp] = 1;
    int att = fp;
    while (sptr[att].size() == 2) {
        if (vis[sptr[att][0]]) att = sptr[att][1];
        else att = sptr[att][0];
        vis[att] = 1;
    } 

    //ricalcolo lo spanning tree
    for (int i = 0; i < N; i++) {
        if (!vis[i] || i == gb.second) sptr[i].clear();
    }
    sptr[gb.second].push_back(fp);
    if(pdr[gb.second] > -1) rs.push_back(pdr[gb.second]);
    fill(pdr.begin(), pdr.end(), -1);
    for (int i : rs) {
        if (vis[i]) continue;
        pdr[i] = gb.second;
        sptr[i].push_back(gb.second);
        sptr[gb.second].push_back(i);
        dfs.push(i);
        while (!dfs.empty()) {
            int x = dfs.top(); dfs.pop();
            if (vis[x]) continue;
            vis[x] = 1;
            if(pdr[x] != -1) {
                sptr[pdr[x]].push_back(x);
                sptr[x].push_back(pdr[x]);
            }
            for (int y : adj[x]) {
                if (vis[y]) continue;
                pdr[y] = x;
                dfs.push(y);
            }
        }
    }
    sol_albero d;
    if (sptr[fp].size() == 1) d.risolvi(N, sptr, fp, -1, gb.second);
    else if (sptr[fp][0] == gb.second) d.risolvi(N, sptr, fp, sptr[fp][1], gb.second);
    else d.risolvi(N, sptr, fp, sptr[fp][0], gb.second);   
}

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