#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
const int nmax = 256;
int n;
std::vector<int> G[nmax + 5];
int d[nmax + 5];
bool sel[nmax + 5];
int t[nmax + 5];
int split, l1, l2;
int find_next_go(int nod)
{
for(auto it : G[nod])
{
if(!sel[it])
{
return it;
}
}
return -1;
}
void dfs(int nod)
{
sel[nod] = true;
int son = find_next_go(nod);
int nr_sons = 0;
while(son!=-1)
{
t[son] = nod;
dfs(son);
son = find_next_go(nod);
++nr_sons;
}
if(nr_sons==2)
{
split = nod;
}
if(!nr_sons)
{
if(l1==-1)
{
l1 = nod;
}
else
{
l2 = nod;
}
}
}
std::vector<int> longest_trip(int N, int D)
{
n = N;
for(int i=0;i<n;i++)
{
G[i].clear();
sel[i] = false;
t[i] = -1;
}
split = -1, l1 = -1, l2 = -1;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(are_connected({i}, {j}))
{
G[i].push_back(j);
G[j].push_back(i);
}
}
}
dfs(0);
vector<int> r;
if(l2==-1)
{
int nod = l1;
r.push_back(l1);
while(nod)
{
nod = t[nod];
r.push_back(nod);
}
return r;
}
vector<int> a,b;
bool ok = false;
for(auto it : G[l1])
{
if(it==0)
{
ok = true;
}
}
if(!ok)
{
swap(l1,l2);
}
int nod = l1;
while(nod!=split)
{
a.push_back(nod);
nod = t[nod];
}
reverse(a.begin(),a.end());
nod = l2;
b.push_back(nod);
while(nod)
{
nod = t[nod];
b.push_back(nod);
}
reverse(b.begin(),b.end());
for(auto it : a)
{
r.push_back(it);
}
for(auto it : b)
{
r.push_back(it);
}
return r;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
174 ms |
1296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
344 KB |
Output is correct |
2 |
Correct |
26 ms |
344 KB |
Output is correct |
3 |
Correct |
129 ms |
604 KB |
Output is correct |
4 |
Correct |
351 ms |
856 KB |
Output is correct |
5 |
Correct |
707 ms |
1248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
344 KB |
Output is correct |
2 |
Correct |
21 ms |
344 KB |
Output is correct |
3 |
Correct |
124 ms |
692 KB |
Output is correct |
4 |
Correct |
357 ms |
856 KB |
Output is correct |
5 |
Correct |
709 ms |
1248 KB |
Output is correct |
6 |
Correct |
7 ms |
344 KB |
Output is correct |
7 |
Correct |
23 ms |
500 KB |
Output is correct |
8 |
Correct |
125 ms |
856 KB |
Output is correct |
9 |
Correct |
251 ms |
964 KB |
Output is correct |
10 |
Correct |
708 ms |
1480 KB |
Output is correct |
11 |
Correct |
698 ms |
1252 KB |
Output is correct |
12 |
Correct |
695 ms |
1352 KB |
Output is correct |
13 |
Correct |
692 ms |
1384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Correct |
27 ms |
344 KB |
Output is correct |
3 |
Correct |
127 ms |
864 KB |
Output is correct |
4 |
Correct |
356 ms |
1112 KB |
Output is correct |
5 |
Correct |
712 ms |
1220 KB |
Output is correct |
6 |
Correct |
9 ms |
344 KB |
Output is correct |
7 |
Correct |
29 ms |
344 KB |
Output is correct |
8 |
Correct |
119 ms |
856 KB |
Output is correct |
9 |
Correct |
297 ms |
960 KB |
Output is correct |
10 |
Correct |
727 ms |
1396 KB |
Output is correct |
11 |
Correct |
657 ms |
1116 KB |
Output is correct |
12 |
Correct |
734 ms |
1396 KB |
Output is correct |
13 |
Correct |
639 ms |
1312 KB |
Output is correct |
14 |
Correct |
8 ms |
344 KB |
Output is correct |
15 |
Incorrect |
2 ms |
344 KB |
Incorrect |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Correct |
24 ms |
340 KB |
Output is correct |
3 |
Partially correct |
124 ms |
1112 KB |
Output is partially correct |
4 |
Partially correct |
320 ms |
968 KB |
Output is partially correct |
5 |
Partially correct |
687 ms |
1652 KB |
Output is partially correct |
6 |
Correct |
9 ms |
596 KB |
Output is correct |
7 |
Correct |
28 ms |
344 KB |
Output is correct |
8 |
Partially correct |
130 ms |
1112 KB |
Output is partially correct |
9 |
Partially correct |
266 ms |
980 KB |
Output is partially correct |
10 |
Partially correct |
730 ms |
1140 KB |
Output is partially correct |
11 |
Partially correct |
671 ms |
1116 KB |
Output is partially correct |
12 |
Partially correct |
716 ms |
1636 KB |
Output is partially correct |
13 |
Partially correct |
741 ms |
1588 KB |
Output is partially correct |
14 |
Incorrect |
0 ms |
344 KB |
Incorrect |
15 |
Halted |
0 ms |
0 KB |
- |