oj.uz

답안 #233977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233977 2020-05-22T14:50:42 Z amiratou 경주 (Race) (IOI11_race) C++14
100 / 100
 1867 ms 83400 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fi first
#define se second
#define ll long long

bool dead[200005];
int s[200005],n,k;
ll ans=LLONG_MAX;
vector<vector<pair<int,int> > > vec;
map<ll,multiset<int> > mymap;
vector<map<ll,int> > best;
int dfs(int node,int p,int s_p,bool flag=0,int d=0,ll h=0){
	if(flag&&(s_p!=-1)){
		if(best[s_p].count(h))best[s_p][h]=min(best[s_p][h],d);
		else best[s_p][h]=d;
	}
	s[node]=1;
	for(auto it:vec[node])
		if(it.fi!=p&&!dead[it.fi])
			s[node]+=dfs(it.fi,node,((!d)?it.fi:s_p),flag,d+1,h+it.se);
	return s[node];
}
int find_cetroid(int node,int p){
	for(auto it:vec[node])
		if(it.fi!=p&&!dead[it.fi]&&s[it.fi]>(n/2))
			return find_cetroid(it.fi,node);
	return node;
}
void solve(int node){
	n=dfs(node,node,-1);
	int r=find_cetroid(node,node);
	mymap.clear();
	dfs(r,r,-1,1);
	for(auto it:vec[r]){
		if(dead[it.fi])continue;
		for(auto it2:best[it.fi])
			mymap[it2.fi].insert(it2.se);
	}
	for(auto it:vec[r]){
		if(dead[it.fi])continue;
		for(auto it3:best[it.fi]){
			if(it3.fi>k)break;
			if(!mymap.count(k-it3.fi))continue;
			auto hk=mymap[k-it3.fi].begin();
			if((best[it.fi].count(k-it3.fi))&&((*hk)==best[it.fi][k-it3.fi]))hk++;
			if(hk!=mymap[k-it3.fi].end())ans=min(ans,(ll)(*hk)+it3.se);
		}
		if(best[it.fi].count(k))ans=min(ans,(ll)best[it.fi][k]);
		best[it.fi].clear();
	}
	dead[r]=1;
	for(auto it:vec[r])
		if(!dead[it.fi])
			solve(it.fi);
}

int best_path(int N, int K, int H[][2], int L[])
{
	best.resize(N);
	k=K;
	vec.resize(N);
	for (int i = 0; i < N-1; ++i)
	{
		vec[H[i][0]].push_back({H[i][1],L[i]});
		vec[H[i][1]].push_back({H[i][0],L[i]});
	}
	solve(0);
	return ((ans==LLONG_MAX)?(-1):ans);
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 7 ms 512 KB Output is correct
22 Correct 8 ms 640 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 7 ms 640 KB Output is correct
25 Correct 7 ms 640 KB Output is correct
26 Correct 7 ms 640 KB Output is correct
27 Correct 6 ms 512 KB Output is correct
28 Correct 7 ms 640 KB Output is correct
29 Correct 7 ms 640 KB Output is correct
30 Correct 7 ms 640 KB Output is correct
31 Correct 7 ms 640 KB Output is correct
32 Correct 7 ms 640 KB Output is correct
33 Correct 8 ms 640 KB Output is correct
34 Correct 7 ms 640 KB Output is correct
35 Correct 7 ms 640 KB Output is correct
36 Correct 7 ms 640 KB Output is correct
37 Correct 7 ms 640 KB Output is correct
38 Correct 7 ms 640 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 358 ms 12780 KB Output is correct
20 Correct 373 ms 12920 KB Output is correct
21 Correct 377 ms 12924 KB Output is correct
22 Correct 340 ms 13176 KB Output is correct
23 Correct 472 ms 13432 KB Output is correct
24 Correct 233 ms 13304 KB Output is correct
25 Correct 299 ms 19016 KB Output is correct
26 Correct 136 ms 21624 KB Output is correct
27 Correct 553 ms 36856 KB Output is correct
28 Correct 1827 ms 83400 KB Output is correct
29 Correct 1777 ms 82040 KB Output is correct
30 Correct 546 ms 36856 KB Output is correct
31 Correct 535 ms 36856 KB Output is correct
32 Correct 620 ms 36824 KB Output is correct
33 Correct 904 ms 25080 KB Output is correct
34 Correct 1567 ms 64508 KB Output is correct

Subtask #4
57.0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 7 ms 512 KB Output is correct
22 Correct 8 ms 640 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 7 ms 640 KB Output is correct
25 Correct 7 ms 640 KB Output is correct
26 Correct 7 ms 640 KB Output is correct
27 Correct 6 ms 512 KB Output is correct
28 Correct 7 ms 640 KB Output is correct
29 Correct 7 ms 640 KB Output is correct
30 Correct 7 ms 640 KB Output is correct
31 Correct 7 ms 640 KB Output is correct
32 Correct 7 ms 640 KB Output is correct
33 Correct 8 ms 640 KB Output is correct
34 Correct 7 ms 640 KB Output is correct
35 Correct 7 ms 640 KB Output is correct
36 Correct 7 ms 640 KB Output is correct
37 Correct 7 ms 640 KB Output is correct
38 Correct 7 ms 640 KB Output is correct
39 Correct 358 ms 12780 KB Output is correct
40 Correct 373 ms 12920 KB Output is correct
41 Correct 377 ms 12924 KB Output is correct
42 Correct 340 ms 13176 KB Output is correct
43 Correct 472 ms 13432 KB Output is correct
44 Correct 233 ms 13304 KB Output is correct
45 Correct 299 ms 19016 KB Output is correct
46 Correct 136 ms 21624 KB Output is correct
47 Correct 553 ms 36856 KB Output is correct
48 Correct 1827 ms 83400 KB Output is correct
49 Correct 1777 ms 82040 KB Output is correct
50 Correct 546 ms 36856 KB Output is correct
51 Correct 535 ms 36856 KB Output is correct
52 Correct 620 ms 36824 KB Output is correct
53 Correct 904 ms 25080 KB Output is correct
54 Correct 1567 ms 64508 KB Output is correct
55 Correct 41 ms 2944 KB Output is correct
56 Correct 26 ms 1664 KB Output is correct
57 Correct 200 ms 12920 KB Output is correct
58 Correct 101 ms 23916 KB Output is correct
59 Correct 603 ms 39672 KB Output is correct
60 Correct 1867 ms 81104 KB Output is correct
61 Correct 584 ms 42360 KB Output is correct
62 Correct 520 ms 36856 KB Output is correct
63 Correct 642 ms 36988 KB Output is correct
64 Correct 1769 ms 49528 KB Output is correct
65 Correct 1442 ms 65784 KB Output is correct
66 Correct 1825 ms 78840 KB Output is correct
67 Correct 334 ms 47592 KB Output is correct
68 Correct 853 ms 61336 KB Output is correct
69 Correct 897 ms 62048 KB Output is correct
70 Correct 828 ms 58616 KB Output is correct