Submission #1130072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130072		irmuun	Make them Meet (EGOI24_makethemmeet)	C++20	57 / 100	1 ms	584 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int>g[n];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    int r=-1;
    for(int i=0;i<n;i++){
        if(g[i].size()==1){
            r=i;
            break;
        }
    }
    if(r==-1) return 0;
    vector<int>d(n,-1),par(n,-1);
    function <void(int,int)> dfs=[&](int x,int p){
        for(int y:g[x]){
            if(d[y]==-1){
                par[y]=x;
                d[y]=d[x]+1;
                dfs(y,x);
            }
        }
    };
    d[r]=0;
    dfs(r,-1);
    vector<vector<int>>ans;
    vector<int>col(n);
    for(int i=0;i<2*n;i++){
        if(i%2==0){
            for(int j=0;j<n;j++){
                if(d[j]%2==1){
                    col[j]=par[j];
                }
                else{
                    col[j]=j;
                }
            }
        }
        else{
            for(int j=0;j<n;j++){
                if(d[j]%2==0&&j!=r){
                    col[j]=par[j];
                }
                else{
                    col[j]=j;
                }
            }
            col[r]=g[r][0];
        }
        ans.pb(col);
    }
    cout<<ans.size()<<"\n";
    for(auto c:ans){
        for(auto i:c){
            cout<<i<<' ';
        }
        cout<<"\n";
    }
}

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