Submission #1065276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065276		LittleOrange	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	938 ms	848 KiB

longesttrip

#include "longesttrip.h"

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct dsu{
    ll c;
    vector<ll> p;
    dsu(ll N):c(N),p(N,-1){}
    ll g(ll i){
        return p[i]<0?i:p[i] = g(p[i]);
    }
    bool m(ll a, ll b){
        a = g(a),b=g(b);
        if(a==b) return false;
        c--;
        if(p[a]>p[b]) swap(a,b);
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};

std::vector<int> longest_trip(int N, int D)
{
    mt19937_64 mt(random_device{}());
    ll n = N;
    if (D==3){
        vector<ll> r(n);
        iota(r.begin(),r.end(),0);
        return r;
    }
    vector<vector<ll>> a(n,vector<ll>(n,0));
    vector<ll> de(n,0);
    dsu d(n);
    for(ll i = 0;i<n;i++){
        for(ll j = i+1;j<n;j++){
            a[i][j] = a[j][i] = are_connected({i},{j});
            if(a[i][j]) d.m(i,j);
            de[i] += a[i][j];
            de[j] += a[i][j];
        }
    }
    if (d.c>1){
        ll g = d.g(0);
        for(ll i = 0;i<n;i++){
            ll j = d.g(i);
            if (d.p[j]<d.p[g]) g = j;
        }
        vector<ll> v;
        for(ll i = 0;i<n;i++){
            if (d.g(i)==g) v.push_back(i);
        }
        return v;
    }
    for(ll i = 0;i<n;i++){
        if(de[i] == 1){
            for(ll j = 0;j<n;j++) if(a[i][j]){
                for(ll k = 0;k<n;k++) if(k!=i&&a[j][k]){
                    vector<ll> v = {i,j,k};
                    for(ll x = 0;x<n;x++) if(x!=i&&x!=j&&x!=k) v.push_back(x);
                    return v;
                }
            }
        }
    }
    vector<ll> ret;
    vector<ll> ord(n);
    iota(ord.begin(),ord.end(),0);
    vector<ll> cur;
    cur.reserve(n);
    ll cnt = 5000;
    while(cnt--){
        shuffle(ord.begin(),ord.end(),mt);
        cur.push_back(ord[0]);
        for(ll i : ord){
            if (a[cur.back()][i]) cur.push_back(i);
        }
        if(cur.size()>ret.size()) ret = cur;
        cur.clear();
        if(ret.size()==n) break;
    }
    return ret;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:82:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   82 |         if(ret.size()==n) break;
      |            ~~~~~~~~~~^~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60