oj.uz

Submission #155828

# Submission time Handle Problem Language Result Execution time Memory
155828 2019-09-30T17:20:31 Z m1sch3f Race (IOI11_race) C++17
100 / 100
 1279 ms 60488 KB 

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

// types - only for stuff used a lot 
using ll = long long;
#define vv vector
#define Pp pair

// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);

// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size()) 
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi

// Debugging

#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif

#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec)  {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}

const int mod = 1e9+7, oo = 1e9;
const ll loo = 1e18;

// Functions 
ll modpow(ll a, ll b) {
	ll ans = 1; // faster modpow than recursive
	for (; b; b/=2,a=a*a%mod)
		if (b&1) ans = (ans*a)%mod;
	return ans;
}
ll gcd(ll a, ll b) {
	while (a) b%=a,swap(a,b);
	return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)


/* 

   ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS

 */

const bool DEBUG = 1;

using vi = vector<int>;

const int N = 200000;
map<int,int> freq;
int K, lift = 0, liftnum = 0;
int ans = oo;
vi adj[N];
int a[N],b[N],c[N];
int sz[N];

int query(int L) {
	L -= lift;
	return freq.count(L)?freq[L]+liftnum:oo;
}

void update(int L, int v) {
	L -= lift;
	if (!freq.count(L)) freq[L] = oo;
	ri(freq[L],v-liftnum);
}

int dfs_subsz(int v, int p) {
	sz[v] = 1;
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p)
			sz[v] += dfs_subsz(w,v);
	}
	return sz[v];
}

void explore(int v, int p, int d, int dd) {
	ri(ans,dd+query(K-d));
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p) explore(w,v,d+c[e],dd+1);
	}	
}

void add(int v, int p, int d, int dd) {
	update(d,dd);
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p) add(w,v,d+c[e],dd+1);
	}	
}

void dfs_solve(int v, int p, bool keep) {
	int bigChild = -1, bigSz = -1, bigc = -1;
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p && sz[w] > bigSz)
			bigSz = sz[w], bigChild = w, bigc = c[e];
	}
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p && w != bigChild)
			dfs_solve(w,v,0);
	}
	if (bigChild != -1) dfs_solve(bigChild,v,1), lift += bigc, liftnum++;
	update(0,0);
	ri(ans,query(K));
	for (int e : adj[v]) {
		int w = a[e]^b[e]^v;
		if (w != p && w != bigChild) {
			explore(w,v,c[e],1);
			add(w,v,c[e],1);
		}
	}
	if (!keep)
		freq = map<int,int>(), lift = liftnum = 0;
}

int best_path(int n, int k, int h[][2], int l[]) {
	K = k;
	f(i,0,n-1) {
		a[i] = h[i][0], b[i] = h[i][1], c[i] = l[i];
		adj[a[i]].pb(i); adj[b[i]].pb(i);
	}
	dfs_subsz(0,-1);
	dfs_solve(0,-1,0);
	return ans==oo?-1:ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5116 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5116 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 300 ms 12380 KB Output is correct
20 Correct 279 ms 12496 KB Output is correct
21 Correct 225 ms 12492 KB Output is correct
22 Correct 213 ms 12408 KB Output is correct
23 Correct 278 ms 12408 KB Output is correct
24 Correct 185 ms 12668 KB Output is correct
25 Correct 114 ms 20812 KB Output is correct
26 Correct 73 ms 27896 KB Output is correct
27 Correct 308 ms 20568 KB Output is correct
28 Correct 435 ms 60488 KB Output is correct
29 Correct 505 ms 58176 KB Output is correct
30 Correct 393 ms 20604 KB Output is correct
31 Correct 369 ms 20572 KB Output is correct
32 Correct 359 ms 20736 KB Output is correct
33 Correct 511 ms 20308 KB Output is correct
34 Correct 658 ms 30424 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5116 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 6 ms 5116 KB Output is correct
11 Correct 6 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 6 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Correct 6 ms 5112 KB Output is correct
19 Correct 6 ms 4984 KB Output is correct
20 Correct 6 ms 5212 KB Output is correct
21 Correct 8 ms 5112 KB Output is correct
22 Correct 8 ms 5208 KB Output is correct
23 Correct 8 ms 5112 KB Output is correct
24 Correct 8 ms 5112 KB Output is correct
25 Correct 8 ms 5240 KB Output is correct
26 Correct 8 ms 5240 KB Output is correct
27 Correct 7 ms 5112 KB Output is correct
28 Correct 8 ms 5112 KB Output is correct
29 Correct 8 ms 5112 KB Output is correct
30 Correct 9 ms 5240 KB Output is correct
31 Correct 7 ms 5112 KB Output is correct
32 Correct 8 ms 5240 KB Output is correct
33 Correct 8 ms 5112 KB Output is correct
34 Correct 7 ms 5240 KB Output is correct
35 Correct 8 ms 5240 KB Output is correct
36 Correct 1 ms 5240 KB Output is correct
37 Correct 7 ms 5240 KB Output is correct
38 Correct 8 ms 5144 KB Output is correct
39 Correct 300 ms 12380 KB Output is correct
40 Correct 279 ms 12496 KB Output is correct
41 Correct 225 ms 12492 KB Output is correct
42 Correct 213 ms 12408 KB Output is correct
43 Correct 278 ms 12408 KB Output is correct
44 Correct 185 ms 12668 KB Output is correct
45 Correct 114 ms 20812 KB Output is correct
46 Correct 73 ms 27896 KB Output is correct
47 Correct 308 ms 20568 KB Output is correct
48 Correct 435 ms 60488 KB Output is correct
49 Correct 505 ms 58176 KB Output is correct
50 Correct 393 ms 20604 KB Output is correct
51 Correct 369 ms 20572 KB Output is correct
52 Correct 359 ms 20736 KB Output is correct
53 Correct 511 ms 20308 KB Output is correct
54 Correct 658 ms 30424 KB Output is correct
55 Correct 26 ms 6008 KB Output is correct
56 Correct 17 ms 5780 KB Output is correct
57 Correct 122 ms 12280 KB Output is correct
58 Correct 68 ms 12400 KB Output is correct
59 Correct 147 ms 32632 KB Output is correct
60 Correct 401 ms 58792 KB Output is correct
61 Correct 427 ms 21980 KB Output is correct
62 Correct 308 ms 20548 KB Output is correct
63 Correct 363 ms 20932 KB Output is correct
64 Correct 982 ms 25124 KB Output is correct
65 Correct 1279 ms 30276 KB Output is correct
66 Correct 453 ms 53224 KB Output is correct
67 Correct 190 ms 21100 KB Output is correct
68 Correct 590 ms 29068 KB Output is correct
69 Correct 537 ms 29304 KB Output is correct
70 Correct 485 ms 28276 KB Output is correct