답안 #750923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750923	2023-05-30T14:34:41 Z	LCJLY	경주 (Race) (IOI11_race)	C++14	9 / 100	193 ms	51876 KB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int>pii;

vector<pii>adj[200005];
multiset<pii>storage[200005];
int offset[200005];
int dist[200005];
int d[200005]; 
int k;
int ans=INT_MAX;

void dp(int index, int par){
	//cout << index << " visit\n";
	storage[index].insert({dist[index],d[index]});
	for(auto it:adj[index]){
		if(it.first==par) continue;
		dist[it.first]=dist[index]+it.second;
		d[it.first]=d[index]+1;
		//cout << index << " " << it.first << " call\n";
		dp(it.first,index);
		//cout << index << " " << it.first << " check\n";
		//swap
		if(storage[it.first].size()>storage[index].size()){
			swap(storage[it.first],storage[index]);
		}
		
		//check
		for(auto it2:storage[it.first]){
			int hold=k-it2.first+dist[index]*2;
			//cout << hold << " target\n";
			pii hold2=*storage[index].lower_bound({hold,0});
			if(hold2.first==hold){
				ans=min(ans,hold2.second+it2.second-d[index]*2);
				//cout << hold2.second<< " " << it2.second << " " << d[index] << "trigger\n";
			}
		}
		
		//merge
		for(auto it2:storage[it.first]){
			storage[index].insert(it2);
		}
	}
	//cout << ans << " " << index << " done\n";
}


int best_path(int n, int K, int H[][2], int L[]){
	k=K;
	
	for(int x=0;x<n-1;x++){
		adj[H[x][0]].push_back({H[x][1],L[x]});
		adj[H[x][1]].push_back({H[x][0],L[x]});
		//cout << H[x][0] << " " << H[x][1] << " edge\n";
	}
	
	dp(0,-1);
	if(ans==INT_MAX) return -1;
	return ans;
}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	8 ms	14420 KB	Output is correct
3	Correct	8 ms	14368 KB	Output is correct
4	Correct	8 ms	14396 KB	Output is correct
5	Correct	8 ms	14336 KB	Output is correct
6	Correct	8 ms	14348 KB	Output is correct
7	Correct	7 ms	14420 KB	Output is correct
8	Correct	8 ms	14420 KB	Output is correct
9	Correct	8 ms	14412 KB	Output is correct
10	Correct	8 ms	14420 KB	Output is correct
11	Correct	8 ms	14316 KB	Output is correct
12	Correct	7 ms	14420 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Correct	8 ms	14400 KB	Output is correct
15	Correct	8 ms	14420 KB	Output is correct
16	Correct	8 ms	14420 KB	Output is correct
17	Correct	7 ms	14400 KB	Output is correct
18	Correct	8 ms	14372 KB	Output is correct

Subtask #2

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	8 ms	14420 KB	Output is correct
3	Correct	8 ms	14368 KB	Output is correct
4	Correct	8 ms	14396 KB	Output is correct
5	Correct	8 ms	14336 KB	Output is correct
6	Correct	8 ms	14348 KB	Output is correct
7	Correct	7 ms	14420 KB	Output is correct
8	Correct	8 ms	14420 KB	Output is correct
9	Correct	8 ms	14412 KB	Output is correct
10	Correct	8 ms	14420 KB	Output is correct
11	Correct	8 ms	14316 KB	Output is correct
12	Correct	7 ms	14420 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Correct	8 ms	14400 KB	Output is correct
15	Correct	8 ms	14420 KB	Output is correct
16	Correct	8 ms	14420 KB	Output is correct
17	Correct	7 ms	14400 KB	Output is correct
18	Correct	8 ms	14372 KB	Output is correct
19	Correct	8 ms	14420 KB	Output is correct
20	Incorrect	8 ms	14400 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #3

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	8 ms	14420 KB	Output is correct
3	Correct	8 ms	14368 KB	Output is correct
4	Correct	8 ms	14396 KB	Output is correct
5	Correct	8 ms	14336 KB	Output is correct
6	Correct	8 ms	14348 KB	Output is correct
7	Correct	7 ms	14420 KB	Output is correct
8	Correct	8 ms	14420 KB	Output is correct
9	Correct	8 ms	14412 KB	Output is correct
10	Correct	8 ms	14420 KB	Output is correct
11	Correct	8 ms	14316 KB	Output is correct
12	Correct	7 ms	14420 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Correct	8 ms	14400 KB	Output is correct
15	Correct	8 ms	14420 KB	Output is correct
16	Correct	8 ms	14420 KB	Output is correct
17	Correct	7 ms	14400 KB	Output is correct
18	Correct	8 ms	14372 KB	Output is correct
19	Incorrect	193 ms	51876 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14420 KB	Output is correct
2	Correct	8 ms	14420 KB	Output is correct
3	Correct	8 ms	14368 KB	Output is correct
4	Correct	8 ms	14396 KB	Output is correct
5	Correct	8 ms	14336 KB	Output is correct
6	Correct	8 ms	14348 KB	Output is correct
7	Correct	7 ms	14420 KB	Output is correct
8	Correct	8 ms	14420 KB	Output is correct
9	Correct	8 ms	14412 KB	Output is correct
10	Correct	8 ms	14420 KB	Output is correct
11	Correct	8 ms	14316 KB	Output is correct
12	Correct	7 ms	14420 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Correct	8 ms	14400 KB	Output is correct
15	Correct	8 ms	14420 KB	Output is correct
16	Correct	8 ms	14420 KB	Output is correct
17	Correct	7 ms	14400 KB	Output is correct
18	Correct	8 ms	14372 KB	Output is correct
19	Correct	8 ms	14420 KB	Output is correct
20	Incorrect	8 ms	14400 KB	Output isn't correct
21	Halted	0 ms	0 KB	-