# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
29370 | 2017-07-19T07:45:24 Z | dereotu | 경주 (Race) (IOI11_race) | C++14 | 3000 ms | 10996 KB |
#include "race.h" #include <bits/stdc++.h> #define pii pair<int,int> #define mp make_pair #define pb push_back #define st first #define nd second #define forr(i,A,B) for(int i=A;i<B;++i) #define space ' ' #define endl '\n' #define LL long long using namespace std; vector <pair<int,int> > adj[200005]; int ans=1e9; int used[200005],sub[200005]; int k; int calc_sub(int x,int y){ sub[x]=1; forr(i,0,adj[x].size()){ if(adj[x][i].nd!=y){ sub[x]+=calc_sub(adj[x][i].nd,x); } } return sub[x]; } int find_centroid(int x,int y,int treesize){ forr(i,0,adj[x].size()){ if(!used[adj[x][i].nd] and adj[x][i].nd!=y and sub[adj[x][i].nd]>treesize/2){ return find_centroid(adj[x][i].nd,x,k); } } return x; } void dfs(int x,int y,int length,int path,map<int,int> &small_map){ if(length>k) return; if(small_map.find(length)==small_map.end()){ small_map[length]=path; } else small_map[length]=min(small_map[length],path); forr(i,0,adj[x].size()){ if(adj[x][i].nd!=y and !used[adj[x][i].nd]){ dfs(adj[x][i].nd,x,length+adj[x][i].st,path+1,small_map); } } } void merge(map<int,int> &a,map<int,int> &b){//iki mapi birleştirip cevabı updateler for(auto it=b.begin();it!=b.end();it++){ if(a.find(k-it->st)!=a.end()){ ans=min(ans,a[k-it->st]+it->nd); } } for(auto it=b.begin();it!=b.end();it++){ if(a.find(it->st)==a.end()){ a[it->st]=it->nd; } else{ a[it->st]=min(a[it->st],it->nd); } } } void calc(int x){//bir subtree için cevabı updateler map<int,int> main_map; main_map[0]=0; forr(i,0,adj[x].size()){ if(!used[adj[x][i].nd]){ map<int,int> sub_map; dfs(x,-1,0,0,sub_map); merge(main_map,sub_map); } } } void solve(int x){ calc_sub(x,-1); int centroid=find_centroid(x,-1,sub[x]); used[x]=1; calc(x); forr(i,0,adj[x].size()){ if(!used[adj[x][i].nd]){ solve(adj[x][i].nd); } } } int best_path(int N, int K, int H[][2], int L[]) { for(int i=0;i<N;i++){ adj[H[i][0]].pb(mp(L[i],H[i][1])); adj[H[i][1]].pb(mp(L[i],H[i][0])); } k=K; solve(0); if(ans==1e9) return -1; else return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5124 KB | Output is correct |
3 | Correct | 6 ms | 5156 KB | Output is correct |
4 | Correct | 6 ms | 5156 KB | Output is correct |
5 | Correct | 8 ms | 5236 KB | Output is correct |
6 | Correct | 7 ms | 5236 KB | Output is correct |
7 | Correct | 6 ms | 5236 KB | Output is correct |
8 | Correct | 6 ms | 5296 KB | Output is correct |
9 | Correct | 7 ms | 5296 KB | Output is correct |
10 | Correct | 6 ms | 5296 KB | Output is correct |
11 | Correct | 6 ms | 5376 KB | Output is correct |
12 | Correct | 6 ms | 5376 KB | Output is correct |
13 | Correct | 6 ms | 5376 KB | Output is correct |
14 | Correct | 7 ms | 5376 KB | Output is correct |
15 | Correct | 6 ms | 5376 KB | Output is correct |
16 | Correct | 7 ms | 5376 KB | Output is correct |
17 | Correct | 6 ms | 5376 KB | Output is correct |
18 | Correct | 7 ms | 5376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5124 KB | Output is correct |
3 | Correct | 6 ms | 5156 KB | Output is correct |
4 | Correct | 6 ms | 5156 KB | Output is correct |
5 | Correct | 8 ms | 5236 KB | Output is correct |
6 | Correct | 7 ms | 5236 KB | Output is correct |
7 | Correct | 6 ms | 5236 KB | Output is correct |
8 | Correct | 6 ms | 5296 KB | Output is correct |
9 | Correct | 7 ms | 5296 KB | Output is correct |
10 | Correct | 6 ms | 5296 KB | Output is correct |
11 | Correct | 6 ms | 5376 KB | Output is correct |
12 | Correct | 6 ms | 5376 KB | Output is correct |
13 | Correct | 6 ms | 5376 KB | Output is correct |
14 | Correct | 7 ms | 5376 KB | Output is correct |
15 | Correct | 6 ms | 5376 KB | Output is correct |
16 | Correct | 7 ms | 5376 KB | Output is correct |
17 | Correct | 6 ms | 5376 KB | Output is correct |
18 | Correct | 7 ms | 5376 KB | Output is correct |
19 | Correct | 5 ms | 5376 KB | Output is correct |
20 | Correct | 6 ms | 5376 KB | Output is correct |
21 | Incorrect | 56 ms | 5376 KB | Output isn't correct |
22 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5124 KB | Output is correct |
3 | Correct | 6 ms | 5156 KB | Output is correct |
4 | Correct | 6 ms | 5156 KB | Output is correct |
5 | Correct | 8 ms | 5236 KB | Output is correct |
6 | Correct | 7 ms | 5236 KB | Output is correct |
7 | Correct | 6 ms | 5236 KB | Output is correct |
8 | Correct | 6 ms | 5296 KB | Output is correct |
9 | Correct | 7 ms | 5296 KB | Output is correct |
10 | Correct | 6 ms | 5296 KB | Output is correct |
11 | Correct | 6 ms | 5376 KB | Output is correct |
12 | Correct | 6 ms | 5376 KB | Output is correct |
13 | Correct | 6 ms | 5376 KB | Output is correct |
14 | Correct | 7 ms | 5376 KB | Output is correct |
15 | Correct | 6 ms | 5376 KB | Output is correct |
16 | Correct | 7 ms | 5376 KB | Output is correct |
17 | Correct | 6 ms | 5376 KB | Output is correct |
18 | Correct | 7 ms | 5376 KB | Output is correct |
19 | Execution timed out | 3045 ms | 10996 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4984 KB | Output is correct |
2 | Correct | 7 ms | 5124 KB | Output is correct |
3 | Correct | 6 ms | 5156 KB | Output is correct |
4 | Correct | 6 ms | 5156 KB | Output is correct |
5 | Correct | 8 ms | 5236 KB | Output is correct |
6 | Correct | 7 ms | 5236 KB | Output is correct |
7 | Correct | 6 ms | 5236 KB | Output is correct |
8 | Correct | 6 ms | 5296 KB | Output is correct |
9 | Correct | 7 ms | 5296 KB | Output is correct |
10 | Correct | 6 ms | 5296 KB | Output is correct |
11 | Correct | 6 ms | 5376 KB | Output is correct |
12 | Correct | 6 ms | 5376 KB | Output is correct |
13 | Correct | 6 ms | 5376 KB | Output is correct |
14 | Correct | 7 ms | 5376 KB | Output is correct |
15 | Correct | 6 ms | 5376 KB | Output is correct |
16 | Correct | 7 ms | 5376 KB | Output is correct |
17 | Correct | 6 ms | 5376 KB | Output is correct |
18 | Correct | 7 ms | 5376 KB | Output is correct |
19 | Correct | 5 ms | 5376 KB | Output is correct |
20 | Correct | 6 ms | 5376 KB | Output is correct |
21 | Incorrect | 56 ms | 5376 KB | Output isn't correct |
22 | Halted | 0 ms | 0 KB | - |