oj.uz

답안 #1065595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1065595 2024-08-19T09:44:32 Z ReLice 가장 긴 여행 (IOI23_longesttrip) C++17
0 / 100
 855 ms 1148 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];
ll 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;
		
		if(d[i] >= (n+1)/2){vis[v] = 0;return;}
		
		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 nn, int D){
	ll i,j;
	
	n=nn;
	
	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(auto i : {0}){
		cl();
		
		d[i] = 1;
		dfs(i);
		
		auto [mx, x] = find();
		
		if(mx < ans){
			mx = ans;
			rt = i;
		}
		if(ans >= (n+1)/2)break;
	}
	
	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 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 344 KB Output is correct
2 Correct 16 ms 344 KB Output is correct
3 Correct 178 ms 456 KB Output is correct
4 Correct 394 ms 496 KB Output is correct
5 Correct 791 ms 928 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 24 ms 344 KB Output is correct
8 Correct 149 ms 600 KB Output is correct
9 Correct 286 ms 488 KB Output is correct
10 Correct 855 ms 724 KB Output is correct
11 Correct 819 ms 892 KB Output is correct
12 Correct 855 ms 1028 KB Output is correct
13 Correct 782 ms 1148 KB Output is correct
14 Correct 5 ms 344 KB Output is correct
15 Incorrect 1 ms 344 KB Incorrect
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -