Submission #1065270

#TimeUsernameProblemLanguageResultExecution timeMemory
1065270LittleOrangeLongest Trip (IOI23_longesttrip)C++17
40 / 100
909 ms848 KiB
#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)); 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); } } 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; } vector<ll> ret; vector<ll> ord(n); iota(ord.begin(),ord.end(),0); vector<ll> cur; cur.reserve(n); ll cnt = 500000/max(n,10); 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:68:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   68 |         if(ret.size()==n) break;
      |            ~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...