Submission #1076215

#TimeUsernameProblemLanguageResultExecution timeMemory
1076215MarwenElarbiLongest Trip (IOI23_longesttrip)C++17
5 / 100
917 ms1108 KiB
#include <bits/stdc++.h> #include "longesttrip.h" using namespace std; #define pb push_back #define fi first #define se second const int nax = 2e5+5; const int MOD = 1e9+7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<int> adj[256]; bool vis[256]; set<int> components[256]; void dfs(int x,int p){ components[p].insert(x); vis[x]=true; for(auto u:adj[x]){ if(vis[u]) continue; dfs(u,p); }return; } std::vector<int> longest_trip(int N, int D) { vector<int> a,b; for (int i = 0; i < N; ++i) { vis[i]=0; adj[i].clear(); components[i].clear(); } for (int i = 0; i < N; ++i) { for (int j = i+1; j < N; ++j) { if(are_connected({i},{j})){ adj[i].pb(j); adj[j].pb(i); }else{ a.pb(i); b.pb(j); } } } pair<int,int> big={-1,-1}; int cnt=0; for (int i = 0; i < N; ++i) { if(vis[i]) continue; cnt++; dfs(i,i); if(big.fi<(int)components[i].size()){ big={(int)components[i].size(),i}; } } vector<int> ans; shuffle(a.begin(),a.end(),rng); shuffle(b.begin(),b.end(),rng); if(a.size()==0){ for (int i = 0; i < N; ++i) { ans.pb(i); } }else{ memset(vis,0,sizeof vis); for(auto u:a){ if(components[big.se].count(u)) { ans.pb(u); vis[u]=true; } } for(auto u:components[big.se]){ if(!vis[u]) ans.pb(u); } for(auto u:b){ if(components[big.se].count(u)){ ans.pb(u); vis[u]=true; } } } return ans; }
#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...