| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1073367 | 2024-08-24T13:36:05 Z | Unforgettablepl | Longest Trip (IOI23_longesttrip) | C++17 | 934 ms | 1676 KB |
#pragma GCC optimize("Ofast","unroll-all-loops")
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> longest_trip(int N,int D){
vector<vector<int>> adj(N);
vector areConnected(N,vector<bool>(N));
for(int i=0;i<N;i++) {
for(int j=i+1;j<N;j++) {
if(are_connected({i},{j})) {
adj[i].emplace_back(j);
adj[j].emplace_back(i);
areConnected[i][j]=areConnected[j][i]=true;
}
}
}
{
// Case 1 if two components
int isTwo = -1;
{
vector<bool> visited(N);
int curr = 0;
function<void(int)> dfs = [&](int x) {
if(visited[x])return;
visited[x]=true;
curr++;
for(int&i:adj[x])dfs(i);
};
dfs(0);
if(curr!=N) {
if(curr>=N-curr)isTwo=curr;
else {
for(int i=0;i<N;i++) {
if(!visited[i]){
isTwo=i;break;
}
}
}
}
}
if(isTwo!=-1) {
vector<bool> visited(N);
vector<int> ans;
function<void(int)> dfs = [&](int x) {
visited[x]=true;
ans.emplace_back(x);
for(int&i:adj[x])if(!visited[i]) {
dfs(i);
return;
}
};
dfs(isTwo);
return ans;
}
}
vector<vector<int>> path(3);
vector<bool> visited(N);
function<int(int,int)> dfs = [&](int x,int def) {
visited[x]=true;
int state = def;
int children = 0;
for(int&i:adj[x])if(!visited[i]) {
children++;
if(children==2) {
assert(dfs(i,2)==2);
state=0;
break;
}
auto ans = dfs(i,def);
if(ans==0) {
state = 0;
break;
}
}
path[state].emplace_back(x);
return state;
};
auto curr = dfs(0,1);
if(curr==1) {
return path[1];
}
assert(curr==0);
if(path[0].size()==1) {
vector<int> ans = path[1];
ans.emplace_back(path[0][0]);
reverse(path[2].begin(),path[2].end());
for(int&i:path[2])ans.emplace_back(i);
return ans;
}
if(!areConnected[path[0][1]][path[1][0]])swap(path[1],path[2]);
assert(areConnected[path[0][1]][path[1][0]]);
path[1].emplace_back(path[0][0]);
path[0].erase(path[0].begin());
reverse(path[0].begin(),path[0].end());
reverse(path[2].begin(),path[2].end());
auto ans = path[0];
for(int&i:path[1])ans.emplace_back(i);
for(int&i:path[2])ans.emplace_back(i);
assert(ans.size()==N);
return ans;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 344 KB | Output is correct |
| 2 | Correct | 187 ms | 988 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 344 KB | Output is correct |
| 2 | Correct | 24 ms | 344 KB | Output is correct |
| 3 | Correct | 166 ms | 600 KB | Output is correct |
| 4 | Correct | 453 ms | 992 KB | Output is correct |
| 5 | Correct | 827 ms | 1140 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 344 KB | Output is correct |
| 2 | Correct | 20 ms | 344 KB | Output is correct |
| 3 | Correct | 152 ms | 600 KB | Output is correct |
| 4 | Correct | 383 ms | 344 KB | Output is correct |
| 5 | Correct | 815 ms | 980 KB | Output is correct |
| 6 | Correct | 7 ms | 344 KB | Output is correct |
| 7 | Correct | 21 ms | 344 KB | Output is correct |
| 8 | Correct | 147 ms | 444 KB | Output is correct |
| 9 | Correct | 342 ms | 488 KB | Output is correct |
| 10 | Correct | 856 ms | 1144 KB | Output is correct |
| 11 | Correct | 834 ms | 760 KB | Output is correct |
| 12 | Correct | 889 ms | 1060 KB | Output is correct |
| 13 | Correct | 854 ms | 1064 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 6 ms | 344 KB | Output is correct |
| 2 | Correct | 26 ms | 344 KB | Output is correct |
| 3 | Correct | 161 ms | 436 KB | Output is correct |
| 4 | Correct | 405 ms | 748 KB | Output is correct |
| 5 | Correct | 887 ms | 1272 KB | Output is correct |
| 6 | Correct | 7 ms | 344 KB | Output is correct |
| 7 | Correct | 28 ms | 432 KB | Output is correct |
| 8 | Correct | 153 ms | 592 KB | Output is correct |
| 9 | Correct | 322 ms | 748 KB | Output is correct |
| 10 | Correct | 839 ms | 1240 KB | Output is correct |
| 11 | Correct | 870 ms | 1104 KB | Output is correct |
| 12 | Correct | 934 ms | 1296 KB | Output is correct |
| 13 | Correct | 833 ms | 1076 KB | Output is correct |
| 14 | Correct | 7 ms | 344 KB | Output is correct |
| 15 | Incorrect | 14 ms | 344 KB | Incorrect |
| 16 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 344 KB | Output is correct |
| 2 | Correct | 20 ms | 344 KB | Output is correct |
| 3 | Partially correct | 146 ms | 680 KB | Output is partially correct |
| 4 | Partially correct | 446 ms | 856 KB | Output is partially correct |
| 5 | Partially correct | 913 ms | 1004 KB | Output is partially correct |
| 6 | Correct | 9 ms | 344 KB | Output is correct |
| 7 | Correct | 28 ms | 344 KB | Output is correct |
| 8 | Partially correct | 124 ms | 344 KB | Output is partially correct |
| 9 | Partially correct | 329 ms | 848 KB | Output is partially correct |
| 10 | Partially correct | 880 ms | 1676 KB | Output is partially correct |
| 11 | Partially correct | 834 ms | 1156 KB | Output is partially correct |
| 12 | Partially correct | 880 ms | 1668 KB | Output is partially correct |
| 13 | Partially correct | 838 ms | 848 KB | Output is partially correct |
| 14 | Incorrect | 1 ms | 344 KB | Incorrect |
| 15 | Halted | 0 ms | 0 KB | - |