Submission #1221540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221540		thelegendary08	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	403 ms	1056 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0;i<n;i++)
#define FOR(i, k, n) for(int i = k;i<n;i++)
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define mp make_pair
#define vpii vector<pii>
#define vvi vector<vi>
#define vb vector<bool>
using namespace std;
const int mxn = 260;
vvi adj(mxn);
std::vector<signed> longest_trip(signed N, signed D)
{
	f0r(i, N){
		adj[i].clear();
	}
	vector<vector<bool>> con(N, vector<bool>(N, false));
	f0r(i, N){
		FOR(j, i+1, N){
			con[i][j] = are_connected({i}, {j});
			con[j][i] = con[i][j];
			if(con[i][j]){
				adj[i].pb(j); adj[j].pb(i);
			}
		}
	}
	f0r(i, N)con[i][i] = 1;
	int sum = 0; 
	f0r(i,N){
		f0r(j,N){
			sum += con[i][j];
		}
	}
	vector<signed>ans;
	if(sum == N * N){
		f0r(i,N)ans.pb(i);
		return ans;
	}
	
	vector<vector<signed>> ccs;
	vb vis(N);
	f0r(i, N){
		if(!vis[i]){
			vector<signed> curcc;
			queue<int>q;
			q.push(i); vis[i]=1; curcc.pb(i);
			while(!q.empty()){
				int node = q.front(); q.pop();
				for(auto u : adj[node]){
					if(vis[u])continue;
					vis[u] = 1; q.push(u); curcc.pb(u);
				}
			}
			ccs.pb(curcc);
		}
	}
	if(ccs.size() > 1){
		int mx = 0; int mxd = 0;
		f0r(i,ccs.size()){
			if(ccs[i].size() > mx){
				mx = ccs[i].size(); mxd = i;
			}
		}
		for(auto u : ccs[mxd])ans.pb(u);
		return ans;
	}
	else{
		int a,b,c;
		f0r(i, N){
			f0r(j, N){
				f0r(k, N){
					if(i != j && i != k && j != k && con[i][j] && con[j][k] && !con[i][k]){
						a=i; b=j; c=k; break;
					}
				}
			}
		}
		
		deque<signed>tmp;
		tmp.pb(a); tmp.pb(b); tmp.pb(c);
		vb vis(N);
		vis[a] = 1; vis[b] = 1; vis[c] = 1;
		// cout<<a<<' '<<b<<' '<<c<<'\n';
		int cnt = 3;
		while(cnt < N){
			if(cnt == N-1){
				int nxt = 0; 
				f0r(i, N){
					if(!vis[i])nxt = i;
				}
				tmp.pb(nxt);
				break;
			}
			else{
				int l = tmp.front(); int r = tmp.back();
				bool ok = 0;
				f0r(i,N){
					if(!vis[i]){
						if(con[l][i] && !con[r][i]){
							ok = 1; tmp.push_front(i); vis[i] = 1; cnt++; break;
						}
						else if(con[r][i] && !con[l][i]){
							ok = 1; tmp.pb(i); vis[i] = 1; cnt++; break;
						}
					}
				}
				if(!ok){
					f0r(i,N){
						f0r(j, N){
							if(!vis[i] && !vis[j] && !con[i][j]){
								vis[i] = 1; vis[j] = 1; cnt+=2; 
								tmp.push_front(i); tmp.pb(j); ok = 1; break;
							}
						}
					}
					if(!ok){
						f0r(i, N){
							if(!vis[i]){
								tmp.pb(i);
							}
						}
						cnt = N; 
					}
				}
			}
		}
		
		while(!tmp.empty()){
			ans.pb(tmp.front()); tmp.pop_front();
		}
		return ans;
	}
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:24:52: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
   24 |                         con[i][j] = are_connected({i}, {j});
      |                                                    ^
longesttrip.cpp:24:52: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
longesttrip.cpp:24:57: warning: narrowing conversion of 'j' from 'long long int' to 'int' [-Wnarrowing]
   24 |                         con[i][j] = are_connected({i}, {j});
      |                                                         ^
longesttrip.cpp:24:57: warning: narrowing conversion of 'j' from 'long long int' to 'int' [-Wnarrowing]

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