oj.uz

답안 #1065577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065577 2024-08-19T09:32:44 Z ReLice 가장 긴 여행 (IOI23_longesttrip) C++17
5 / 100
 947 ms 1132 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];
ll vis[N];

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 197 ms 620 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 25 ms 344 KB Output is correct
3 Correct 157 ms 708 KB Output is correct
4 Correct 424 ms 496 KB Output is correct
5 Correct 885 ms 1132 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 344 KB Output is correct
2 Correct 18 ms 344 KB Output is correct
3 Correct 128 ms 456 KB Output is correct
4 Correct 438 ms 460 KB Output is correct
5 Correct 880 ms 732 KB Output is correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 21 ms 344 KB Output is correct
3 Correct 163 ms 344 KB Output is correct
4 Correct 438 ms 704 KB Output is correct
5 Correct 830 ms 1044 KB Output is correct
6 Correct 8 ms 356 KB Output is correct
7 Correct 29 ms 344 KB Output is correct
8 Correct 172 ms 600 KB Output is correct
9 Correct 336 ms 344 KB Output is correct
10 Correct 882 ms 732 KB Output is correct
11 Correct 938 ms 884 KB Output is correct
12 Correct 932 ms 856 KB Output is correct
13 Correct 947 ms 1064 KB Output is correct
14 Correct 7 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 24 ms 344 KB Output is correct
3 Partially correct 158 ms 340 KB Output is partially correct
4 Partially correct 444 ms 596 KB Output is partially correct
5 Partially correct 884 ms 880 KB Output is partially correct
6 Incorrect 0 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -