Submission #1329452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1329452		liptonek	Make them Meet (EGOI24_makethemmeet)	C++20	46.53 / 100	7972 ms	14756 KiB

Main

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

bool ins[105][105];

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m;
    cin>>n>>m;

    vector<vector<int>> adj(n);
    vector<pair<int,int>> hotel;

    for(int i=0; i<m; i++) 
    {
        int u,v;
        cin>>u>>v;
    
        adj[u].push_back(v);
        adj[v].push_back(u);
    
        hotel.push_back({min(u,v),max(u,v)});
    }

    vector<vector<int>> dist(n,vector<int>(n,1e9));

    for(int i=0; i<n; i++) 
    {
        dist[i][i]=0;
    }

    for(auto& e : hotel) 
    {
        dist[e.first][e.second]=dist[e.second][e.first]=1;
    }

    for(int k=0; k<n; k++)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }

    vector<pair<int,int>> s;

    for(int i=0; i<n; i++) 
    {
        for(int j=i+1; j<n; j++) 
        {
            s.push_back({i,j});
        
            ins[i][j]=true;
        }
    }

    vector<vector<int>> results;
    
    mt19937 rng(1337);

    while(!s.empty() && results.size()<20000) 
    {
        vector<pair<int,int>> edges;

        for(auto& e : hotel) 
        {
            if(ins[e.first][e.second]) 
            {
                edges.push_back(e);
            }
        }

        vector<pair<int,int>> best;
        
        int xr=-1;
        long long nds=2e18;
        int trials=edges.empty() ? 40 : 100;

        if(s.size()>2000) 
        {
            trials=20; 
        }

        for(int t=0; t<trials; t++) 
        {
            vector<pair<int,int>> current;
            vector<bool> used(n,false);

            if(!edges.empty()) 
            {
                shuffle(edges.begin(),edges.end(),rng);
            
                for(auto& e : edges) 
                {
                    if(!used[e.first] && !used[e.second]) 
                    {
                        used[e.first]=used[e.second]=true;
                    
                        current.push_back(e);
                    }
                }
            } 
            else 
            {
                pair<int,int> cp=s[0]; 
                
                int dn=1e9;

                for(auto& p : s) 
                {
                    if(dist[p.first][p.second]<dn) 
                    { 
                        dn=dist[p.first][p.second]; 
                        cp=p; 
                    }
                }

                vector<int> neighbors=adj[cp.first];

                shuffle(neighbors.begin(),neighbors.end(),rng);

                for(int v : neighbors) 
                {
                    if(dist[v][cp.second]<dist[cp.first][cp.second]) 
                    {
                        current.push_back({min(cp.first,v),max(cp.first,v)});
                    
                        used[cp.first]=used[v]=true;
                    
                        break;
                    }
                }
            }

            static vector<int> e;

            if(e.size()!=hotel.size()) 
            {
                e.resize(hotel.size()); 
                iota(e.begin(),e.end(),0);
            }

            shuffle(e.begin(),e.end(),rng);
            
            for(int idx : e) 
            {
                int u=hotel[idx].first;
                int v=hotel[idx].second;
            
                if(!used[u] && !used[v]) 
                { 
                    used[u]=used[v]=true; 
                    
                    current.push_back({u,v}); 
                }
            }

            int res=0; 
            long long dsum=0;

            static int p[105]; 
            
            for(int i=0; i<n; i++) 
            {
                p[i]=i;
            }

            for(auto& e : current) 
            { 
                p[e.first]=e.second; 
                p[e.second]=e.first; 
            }

            for(auto& uv : s) 
            {
                if(p[uv.first]==uv.second) 
                {
                    res++;
                }
                else 
                {
                    dsum+=dist[p[uv.first]][p[uv.second]];
                }
            }

            if(res>xr ||(res==xr && dsum<nds)) 
            {
                xr=res; 
                nds=dsum; 
                best=current;
            }
        }

        static int fp[105]; 
        
        for(int i=0; i<n; i++) 
        {
            fp[i]=i;
        }

        for(auto& e : best) 
        { 
            fp[e.first]=e.second; 
            fp[e.second]=e.first; 
        }

        vector<pair<int,int>> ns;
        
        for(int i=0; i<n; i++) 
        {
            for(int j=i+1; j<n; j++) 
            {
                ins[i][j]=false;
            }
        }
        
        for(auto& uv : s) 
        {
            if(fp[uv.first]==uv.second) 
            {
                continue;
            }
        
            int nu=fp[uv.first],nv=fp[uv.second];
        
            if(nu>nv) 
            {
                swap(nu,nv);
            }
        
            if(!ins[nu][nv]) 
            { 
                ins[nu][nv]=true; 
                
                ns.push_back({nu,nv}); 
            }
        }

        s=ns;

        vector<int> colors(n);
        vector<bool> colored(n,false);

        int cid=1;

        for(auto& e : best) 
        {
            colors[e.first]=colors[e.second]=cid++;
            colored[e.first]=colored[e.second]=true;
        }
        
        for(int i=0; i<n; i++) 
        {
            if(!colored[i]) 
            {
                colors[i]=cid++;
            }
        }
        
        results.push_back(colors);
    }

    cout<<results.size()<<endl;
    
    for(auto& move : results) 
    {
        for(int i=0; i<n; i++) 
        {
            cout<<move[i]<<(i==n-1 ? "" : " ");
        }

        cout<<endl;
    }

    return 0;
}

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