oj.uz

답안 #1065542

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065542 2024-08-19T09:04:48 Z ReLice 가장 긴 여행 (IOI23_longesttrip) C++17
5 / 100
 936 ms 1476 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];

void dfs(ll v){
	for(auto i : g[v]){
		if(d[i] != inf)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 != p[x]){
		v.pb(x);
		x = p[x];
	}
	v.pb(x);
	
	return v;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 23 ms 344 KB Output is correct
3 Correct 135 ms 344 KB Output is correct
4 Correct 389 ms 344 KB Output is correct
5 Correct 903 ms 1476 KB Output is correct

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 31 ms 344 KB Output is correct
3 Correct 161 ms 340 KB Output is correct
4 Correct 431 ms 692 KB Output is correct
5 Correct 912 ms 960 KB Output is correct
6 Incorrect 1 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 23 ms 344 KB Output is correct
3 Correct 165 ms 344 KB Output is correct
4 Correct 426 ms 592 KB Output is correct
5 Correct 903 ms 1060 KB Output is correct
6 Correct 9 ms 344 KB Output is correct
7 Correct 33 ms 344 KB Output is correct
8 Correct 155 ms 344 KB Output is correct
9 Correct 324 ms 960 KB Output is correct
10 Correct 908 ms 1032 KB Output is correct
11 Correct 848 ms 1220 KB Output is correct
12 Correct 936 ms 832 KB Output is correct
13 Correct 849 ms 984 KB Output is correct
14 Correct 10 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 9 ms 344 KB Output is correct
2 Correct 27 ms 344 KB Output is correct
3 Partially correct 163 ms 344 KB Output is partially correct
4 Partially correct 429 ms 480 KB Output is partially correct
5 Partially correct 860 ms 828 KB Output is partially correct
6 Incorrect 1 ms 344 KB Incorrect
7 Halted 0 ms 0 KB -