oj.uz

Submission #839930

# Submission time Handle Problem Language Result Execution time Memory
839930 2023-08-30T21:20:08 Z pere_gil Longest Trip (IOI23_longesttrip) C++17
15 / 100
 962 ms 756 KB 
#include "longesttrip.h"
#include "bits/stdc++.h"
using namespace std;

#define vi vector<int>
#define ii pair<int,int>

const int mxn=257;
vector<int> adj[mxn];

ii dfs(int u, vector<bool> &vis, vi &res, bool sw){
  vis[u]=true;
  ii best={0,u};
  int nxt=u;
  for(int v: adj[u]){
    if(vis[v]) continue;
    ii act=dfs(v,vis,res,sw);
    if(act.first+1>best.first) best={act.first+1,act.second},nxt=v;
  }
  
  if(sw && nxt!=u) res.push_back(nxt);
  
  return best;
}

vi longest_trip(int n, int d){
  for(int i=0;i<n;i++) adj[i].clear();
  for(int i=0;i<n;i++)
    for(int j=i+1;j<n;j++)
      if(are_connected({i},{j}))
	adj[i].push_back(j),adj[j].push_back(i);

  vector<bool> first(n,false),second(n,false);
  vector<int> res;
  for(int i=0;i<n;i++){
    if(first[i]) continue;
    vi act;
    int st=dfs(i,first,act,false).second;
    dfs(st,second,act,true);
    act.push_back(st);

    if(act.size()>res.size()) res=act;
  }
  
  return res;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 161 ms 524 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 208 KB Output is correct
2 Correct 39 ms 208 KB Output is correct
3 Correct 173 ms 208 KB Output is correct
4 Correct 412 ms 364 KB Output is correct
5 Correct 701 ms 500 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 43 ms 208 KB Output is correct
3 Correct 110 ms 308 KB Output is correct
4 Correct 457 ms 336 KB Output is correct
5 Correct 817 ms 564 KB Output is correct
6 Correct 12 ms 208 KB Output is correct
7 Correct 28 ms 208 KB Output is correct
8 Correct 210 ms 312 KB Output is correct
9 Correct 332 ms 328 KB Output is correct
10 Correct 801 ms 544 KB Output is correct
11 Correct 956 ms 596 KB Output is correct
12 Correct 888 ms 592 KB Output is correct
13 Correct 962 ms 600 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 208 KB Output is correct
2 Correct 34 ms 208 KB Output is correct
3 Correct 168 ms 304 KB Output is correct
4 Correct 494 ms 336 KB Output is correct
5 Correct 810 ms 568 KB Output is correct
6 Correct 11 ms 208 KB Output is correct
7 Correct 29 ms 208 KB Output is correct
8 Correct 216 ms 208 KB Output is correct
9 Correct 417 ms 312 KB Output is correct
10 Correct 940 ms 756 KB Output is correct
11 Correct 734 ms 480 KB Output is correct
12 Correct 858 ms 580 KB Output is correct
13 Correct 714 ms 504 KB Output is correct
14 Correct 12 ms 208 KB Output is correct
15 Correct 15 ms 208 KB Output is correct
16 Incorrect 11 ms 208 KB Incorrect
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 208 KB Output is correct
2 Correct 52 ms 208 KB Output is correct
3 Partially correct 158 ms 208 KB Output is partially correct
4 Partially correct 316 ms 696 KB Output is partially correct
5 Partially correct 910 ms 600 KB Output is partially correct
6 Correct 12 ms 208 KB Output is correct
7 Correct 30 ms 208 KB Output is correct
8 Partially correct 194 ms 324 KB Output is partially correct
9 Partially correct 338 ms 328 KB Output is partially correct
10 Partially correct 901 ms 528 KB Output is partially correct
11 Partially correct 858 ms 576 KB Output is partially correct
12 Partially correct 674 ms 608 KB Output is partially correct
13 Partially correct 895 ms 608 KB Output is partially correct
14 Correct 9 ms 208 KB Output is correct
15 Correct 16 ms 208 KB Output is correct
16 Incorrect 1 ms 208 KB Incorrect
17 Halted 0 ms 0 KB -