Submission #100398

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100398	2019-03-10T22:36:06 Z	SuperJumbo	Race (IOI11_race)	C++14	21 / 100	84 ms	16248 KB

race

#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define NMAX 1001
#else
#define NMAX 200005
#endif
#define inf (INT_MAX>>2)
#define ll long long
#define add push_back
#define mp make_pair
#include "race.h"
using namespace std;
vector<vector<pair<int,int>>> g;
int tot, k, ans; 
int sz[NMAX], cen[NMAX];
unordered_map<int,int> all,sub;
 
void dfs(int node,int par){
    sz[node] = 1;
    for(auto e:g[node]){
    	int x = e.first;
        if(x == par || cen[x] )continue;
        dfs(x,node);
        sz[node] += sz[x];
    }
    tot = max(tot,sz[node]);
}
int centroid(int node,int par){
    for(auto e:g[node]){
    	int x = e.first;
        if(x!=par && sz[x]> tot/2 && !cen[x]){
            return centroid(x,node);
        }
    }
    cen[node] = 1;
    return node;
}
void dfs2(int node, int par, int cc, int len){
	if(len == k) ans = min(ans, cc);
	if(len >= k) return;
	if(all[k-len]) ans = min(ans,all[k-len]+cc);
	if(!sub[len])  sub[len] = cc;
	sub[len] = min(sub[len],cc);
	for(auto e:g[node]){
		int x = e.first;
		if(!cen[x] && x != par)
			dfs2(x,node,cc+1,len + e.second);
	}
 
 
}
void dcmp(int node,int par){
    tot = 0;
    dfs(node,par);
    int c = centroid(node,par);
    all.clear();
    for(auto e :g[c]){
    	int x  = e.first;
    	if(cen[x])continue;
    	sub.clear();
    	dfs2(x,c,1,e.second);
    	for(auto u:sub) 
    		all[u.first] = all[u.first] == 0 ? u.second : min(all[u.first],u.second);
    }
    for(auto e:g[c]){
    	int x = e.first;
    	if(!cen[x]) dcmp(x,c);
    }
}
int best_path(int n,int K,int h[][2] ,int L[]) {
	k  = K;
    g.resize(n);
    for(int i = 0 ;i<n-1;i++){
    	int u = h[i][0], v = h[i][1];
        g[u].add(mp(v,L[i]));g[v].add(mp(u,L[i]));
    }
    memset(cen,0,sizeof(cen));
    ans = inf;
    dcmp(0,-1);
  	ans = ans == inf ? -1: ans;
    return ans;
  
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	380 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	380 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	4 ms	384 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct
23	Correct	3 ms	384 KB	Output is correct
24	Correct	3 ms	384 KB	Output is correct
25	Correct	5 ms	512 KB	Output is correct
26	Correct	3 ms	384 KB	Output is correct
27	Correct	3 ms	460 KB	Output is correct
28	Correct	6 ms	512 KB	Output is correct
29	Correct	4 ms	512 KB	Output is correct
30	Correct	5 ms	512 KB	Output is correct
31	Correct	7 ms	512 KB	Output is correct
32	Correct	6 ms	512 KB	Output is correct
33	Correct	6 ms	512 KB	Output is correct
34	Correct	4 ms	384 KB	Output is correct
35	Correct	4 ms	384 KB	Output is correct
36	Correct	4 ms	384 KB	Output is correct
37	Correct	4 ms	512 KB	Output is correct
38	Correct	6 ms	512 KB	Output is correct

Subtask #3
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	380 KB	Output is correct
19	Runtime error	84 ms	16248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 57.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	412 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	3 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	3 ms	380 KB	Output is correct
19	Correct	3 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	4 ms	384 KB	Output is correct
22	Correct	3 ms	384 KB	Output is correct
23	Correct	3 ms	384 KB	Output is correct
24	Correct	3 ms	384 KB	Output is correct
25	Correct	5 ms	512 KB	Output is correct
26	Correct	3 ms	384 KB	Output is correct
27	Correct	3 ms	460 KB	Output is correct
28	Correct	6 ms	512 KB	Output is correct
29	Correct	4 ms	512 KB	Output is correct
30	Correct	5 ms	512 KB	Output is correct
31	Correct	7 ms	512 KB	Output is correct
32	Correct	6 ms	512 KB	Output is correct
33	Correct	6 ms	512 KB	Output is correct
34	Correct	4 ms	384 KB	Output is correct
35	Correct	4 ms	384 KB	Output is correct
36	Correct	4 ms	384 KB	Output is correct
37	Correct	4 ms	512 KB	Output is correct
38	Correct	6 ms	512 KB	Output is correct
39	Runtime error	84 ms	16248 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

Submission #100398

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 22.0

Subtask #4 0 / 57.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 22.0

Subtask #4
0 / 57.0