oj.uz

Submission #1065580

# Submission time Handle Problem Language Result Execution time Memory
1065580 2024-08-19T09:34:30 Z ReLice Longest Trip (IOI23_longesttrip) C++17
5 / 100
 1000 ms 1552 KB 
#include "longesttrip.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define ins insert
#define fr first
#define sc second
#define vll vector<ll>
#define sz size()
using namespace std;

const ll N = 260;
const ll inf = 1e9 + 7;

vector<vll> g(N);
ll d[N],p[N];
bool vis[N];

void dfs(ll v){
	vis[v] = 1;
	for(auto i : g[v]){
		if(d[i] != inf || (!vis[i] && d[i] < d[v] + 1))continue;
		
		p[i] = v;
		d[i] = d[v] + 1;
		
		dfs(i);
	}
	vis[v] = 0;
}

void cl(){
	for(ll i=0;i<N;i++){
		d[i] = inf;
		p[i] = i;
	}
}

pair<ll,ll> find(){
	ll mx = -1, x = 0;
	
	for(ll i=0;i<N;i++){
		if(d[i] != inf && d[i] > mx){
			mx = d[i];
			x = i;
		}
	}
	
	return {mx, x};
}

vector<int> longest_trip(int n, int D){
	ll i,j;
	
	for(i=0;i<n;i++) g[i].clear();
	for(i=0;i<n;i++){
		for(j=i+1;j<n;j++){
			if(are_connected({i},{j})){
				g[i].pb(j);
				g[j].pb(i);
			}
		}
	}
	
	ll rt = 0, ans = 0;
	
	for(i=0;i<n;i++){
		cl();
		
		d[i] = 0;
		dfs(i);
		
		auto [mx, x] = find();
		
		if(mx < ans){
			mx = ans;
			rt = i;
		}
	}
	
	cl();
	
	d[rt] = 0;
	dfs(rt);
	
	auto [mx, x] = find();
	
	vll v;
	while(x != rt){
		v.pb(x);
		x = p[x];
	}
	v.pb(rt);
	
	return v;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 201 ms 1156 KB Output is correct

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 152 ms 700 KB Output is correct
4 Correct 421 ms 720 KB Output is correct
5 Correct 933 ms 1068 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 344 KB Output is correct
2 Correct 17 ms 340 KB Output is correct
3 Correct 171 ms 600 KB Output is correct
4 Correct 466 ms 724 KB Output is correct
5 Execution timed out 1016 ms 1552 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 28 ms 344 KB Output is correct
3 Correct 185 ms 344 KB Output is correct
4 Correct 461 ms 724 KB Output is correct
5 Correct 975 ms 1096 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 27 ms 344 KB Output is correct
8 Correct 143 ms 344 KB Output is correct
9 Correct 331 ms 724 KB Output is correct
10 Correct 921 ms 1480 KB Output is correct
11 Correct 851 ms 1236 KB Output is correct
12 Correct 910 ms 1508 KB Output is correct
13 Correct 927 ms 1048 KB Output is correct
14 Correct 9 ms 344 KB Output is correct
15 Incorrect 2 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Partially correct 152 ms 600 KB Output is partially correct
4 Partially correct 483 ms 492 KB Output is partially correct
5 Partially correct 982 ms 1252 KB Output is partially correct
6 Incorrect 0 ms 340 KB Incorrect
7 Halted 0 ms 0 KB -