# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1076142 | 2024-08-26T11:24:36 Z | MarwenElarbi | Longest Trip (IOI23_longesttrip) | C++17 | 0 ms | 0 KB |
#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; bool are_connected(std::vector<int> A, std::vector<int> B); vector<int> adj[256]; bool vis[256]; vector<int> components[256]; void dfs(int x,int p){ components[p].pb(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) { for (int i = 0; i < N; ++i) { vis[i]=0; adj[i].clear(); components.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); } } } pair<int,int> big={-1,-1}; for (int i = 0; i < N; ++i) { if(vis[i]) continue; dfs(i,i); if(big.fi<(int)components[i].size()){ big={(int)components[i].size(),i}; } } vector<int> ans; for(auto u:components[big.se]){ ans.pb(u); } return ans; }