oj.uz

Submission #100403

# Submission time Handle Problem Language Result Execution time Memory
100403 2019-03-10T22:53:24 Z SuperJumbo Race (IOI11_race) C++14
9 / 100
 3000 ms 21260 KB 
 #include <bits/stdc++.h>
#define NMAX 500001
#define inf (INT_MAX>>2)
#define ll long long
#define add push_back
#define mp make_pair
#include "race.h"
using namespace std;
#define min(a,b) (a > b ? b : a) 
vector<pair<int,int>> g[NMAX];
int tot, k, ans; 
int sz[NMAX], cen[NMAX];
int all[NMAX];
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, unordered_map<int,int> & sub){
	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,sub);
	}
 
 
}
void dcmp(int node,int par){
    tot = 0;
    dfs(node,par);
    int c = centroid(node,par);
    memset(all,0,sizeof(all));
    for(auto e :g[c]){
    	int x  = e.first;
    	if(cen[x])continue;
    	unordered_map<int,int> sub;
    	dfs2(x,c,1,e.second, sub);
    	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;
    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 23 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 25 ms 16000 KB Output is correct
4 Correct 24 ms 16000 KB Output is correct
5 Correct 25 ms 16000 KB Output is correct
6 Correct 24 ms 16000 KB Output is correct
7 Correct 26 ms 16000 KB Output is correct
8 Correct 24 ms 16000 KB Output is correct
9 Correct 30 ms 15992 KB Output is correct
10 Correct 25 ms 15972 KB Output is correct
11 Correct 25 ms 16000 KB Output is correct
12 Correct 24 ms 16000 KB Output is correct
13 Correct 23 ms 16000 KB Output is correct
14 Correct 24 ms 16000 KB Output is correct
15 Correct 25 ms 16000 KB Output is correct
16 Correct 24 ms 16000 KB Output is correct
17 Correct 24 ms 16000 KB Output is correct
18 Correct 24 ms 15972 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 25 ms 16000 KB Output is correct
4 Correct 24 ms 16000 KB Output is correct
5 Correct 25 ms 16000 KB Output is correct
6 Correct 24 ms 16000 KB Output is correct
7 Correct 26 ms 16000 KB Output is correct
8 Correct 24 ms 16000 KB Output is correct
9 Correct 30 ms 15992 KB Output is correct
10 Correct 25 ms 15972 KB Output is correct
11 Correct 25 ms 16000 KB Output is correct
12 Correct 24 ms 16000 KB Output is correct
13 Correct 23 ms 16000 KB Output is correct
14 Correct 24 ms 16000 KB Output is correct
15 Correct 25 ms 16000 KB Output is correct
16 Correct 24 ms 16000 KB Output is correct
17 Correct 24 ms 16000 KB Output is correct
18 Correct 24 ms 15972 KB Output is correct
19 Correct 16 ms 16000 KB Output is correct
20 Correct 24 ms 16000 KB Output is correct
21 Correct 118 ms 16184 KB Output is correct
22 Correct 113 ms 16092 KB Output is correct
23 Correct 122 ms 16092 KB Output is correct
24 Incorrect 110 ms 16000 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 25 ms 16000 KB Output is correct
4 Correct 24 ms 16000 KB Output is correct
5 Correct 25 ms 16000 KB Output is correct
6 Correct 24 ms 16000 KB Output is correct
7 Correct 26 ms 16000 KB Output is correct
8 Correct 24 ms 16000 KB Output is correct
9 Correct 30 ms 15992 KB Output is correct
10 Correct 25 ms 15972 KB Output is correct
11 Correct 25 ms 16000 KB Output is correct
12 Correct 24 ms 16000 KB Output is correct
13 Correct 23 ms 16000 KB Output is correct
14 Correct 24 ms 16000 KB Output is correct
15 Correct 25 ms 16000 KB Output is correct
16 Correct 24 ms 16000 KB Output is correct
17 Correct 24 ms 16000 KB Output is correct
18 Correct 24 ms 15972 KB Output is correct
19 Execution timed out 3042 ms 21260 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16000 KB Output is correct
2 Correct 24 ms 16000 KB Output is correct
3 Correct 25 ms 16000 KB Output is correct
4 Correct 24 ms 16000 KB Output is correct
5 Correct 25 ms 16000 KB Output is correct
6 Correct 24 ms 16000 KB Output is correct
7 Correct 26 ms 16000 KB Output is correct
8 Correct 24 ms 16000 KB Output is correct
9 Correct 30 ms 15992 KB Output is correct
10 Correct 25 ms 15972 KB Output is correct
11 Correct 25 ms 16000 KB Output is correct
12 Correct 24 ms 16000 KB Output is correct
13 Correct 23 ms 16000 KB Output is correct
14 Correct 24 ms 16000 KB Output is correct
15 Correct 25 ms 16000 KB Output is correct
16 Correct 24 ms 16000 KB Output is correct
17 Correct 24 ms 16000 KB Output is correct
18 Correct 24 ms 15972 KB Output is correct
19 Correct 16 ms 16000 KB Output is correct
20 Correct 24 ms 16000 KB Output is correct
21 Correct 118 ms 16184 KB Output is correct
22 Correct 113 ms 16092 KB Output is correct
23 Correct 122 ms 16092 KB Output is correct
24 Incorrect 110 ms 16000 KB Output isn't correct
25 Halted 0 ms 0 KB -