oj.uz

Submission #875600

# Submission time Handle Problem Language Result Execution time Memory
875600 2023-11-20T06:52:13 Z aykhn Race (IOI11_race) C++17
100 / 100
 684 ms 51516 KB 
#include "race.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;
 
#define pb push_back
#define ins insert
#define fi first
#define se second
#define mod (ll)(1e9 + 7)
#define mxn (ll)(2e5 + 5)
#define inf (ll)(0x3F3F3F3F)

int n, k;
vector<pii> adj[mxn];
int sz[mxn];
int used[mxn];

void getsize(int a, int p)
{
	sz[a] = 1;
	for (pii v : adj[a])
	{
		if (used[v.fi] || v.fi == p) continue;
		getsize(v.fi, a);
		sz[a] += sz[v.fi];
	}
}

int findcent(int a, int p, int curn)
{
	for (pii v : adj[a])
	{
		if (used[v.fi] || v.fi == p) continue;
		if (sz[v.fi] > curn/2) return findcent(v.fi, a, curn);
	}
	return a;
}
vector<pii> arr;
map<int, int> mp;
int res = inf;

void init(int a, int p, int w, int w1)
{
	if (mp.find(k - w) != mp.end())
	{
		res = min(res, mp[k - w] + w1);
	}
	arr.pb({w, w1});
	for (pii v : adj[a])
	{
		if (used[v.fi] || v.fi == p) continue;
		init(v.fi, a, w + v.se, w1 + 1);
	}
}

void maincent(int a)
{
	mp.clear();
	getsize(a, a);
	int c = findcent(a, a, sz[a]);
	mp[0] = 0;
	for (pii v : adj[c])
	{
		if (used[v.fi]) continue;
		arr.clear();
		init(v.fi, c, v.se, 1);
		for (pii x : arr)
		{
			if (mp.find(x.fi) == mp.end()) mp[x.fi] = x.se;
			else mp[x.fi] = min(mp[x.fi], (int)x.se);
		}
	}
	used[c] = 1;
	for (pii v : adj[c])
	{
		if (used[v.fi]) continue;
		maincent(v.fi);
	}

}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N;
	k = K;
	for (int i = 0; i < n - 1; i++)
	{
		adj[H[i][0]].pb({H[i][1], L[i]});
		adj[H[i][1]].pb({H[i][0], L[i]});
	}
	maincent(0);
	return (res == inf ? -1 : res);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10344 KB Output is correct
7 Correct 2 ms 10328 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 2 ms 10332 KB Output is correct
10 Correct 2 ms 10356 KB Output is correct
11 Correct 2 ms 10332 KB Output is correct
12 Correct 3 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 2 ms 10332 KB Output is correct
15 Correct 2 ms 10160 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10172 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10344 KB Output is correct
7 Correct 2 ms 10328 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 2 ms 10332 KB Output is correct
10 Correct 2 ms 10356 KB Output is correct
11 Correct 2 ms 10332 KB Output is correct
12 Correct 3 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 2 ms 10332 KB Output is correct
15 Correct 2 ms 10160 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10172 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 2 ms 10332 KB Output is correct
20 Correct 2 ms 10332 KB Output is correct
21 Correct 4 ms 10356 KB Output is correct
22 Correct 3 ms 10332 KB Output is correct
23 Correct 5 ms 10704 KB Output is correct
24 Correct 4 ms 10332 KB Output is correct
25 Correct 3 ms 10332 KB Output is correct
26 Correct 4 ms 10332 KB Output is correct
27 Correct 3 ms 10332 KB Output is correct
28 Correct 3 ms 10352 KB Output is correct
29 Correct 3 ms 10352 KB Output is correct
30 Correct 3 ms 10332 KB Output is correct
31 Correct 3 ms 10468 KB Output is correct
32 Correct 4 ms 10332 KB Output is correct
33 Correct 5 ms 10588 KB Output is correct
34 Correct 3 ms 10332 KB Output is correct
35 Correct 4 ms 10332 KB Output is correct
36 Correct 3 ms 10476 KB Output is correct
37 Correct 4 ms 10380 KB Output is correct
38 Correct 3 ms 10584 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10344 KB Output is correct
7 Correct 2 ms 10328 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 2 ms 10332 KB Output is correct
10 Correct 2 ms 10356 KB Output is correct
11 Correct 2 ms 10332 KB Output is correct
12 Correct 3 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 2 ms 10332 KB Output is correct
15 Correct 2 ms 10160 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10172 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 166 ms 19948 KB Output is correct
20 Correct 160 ms 20184 KB Output is correct
21 Correct 168 ms 20008 KB Output is correct
22 Correct 140 ms 20180 KB Output is correct
23 Correct 210 ms 20424 KB Output is correct
24 Correct 106 ms 19240 KB Output is correct
25 Correct 135 ms 25036 KB Output is correct
26 Correct 80 ms 27508 KB Output is correct
27 Correct 202 ms 26176 KB Output is correct
28 Correct 624 ms 51516 KB Output is correct
29 Correct 612 ms 50304 KB Output is correct
30 Correct 206 ms 26212 KB Output is correct
31 Correct 248 ms 26448 KB Output is correct
32 Correct 222 ms 26484 KB Output is correct
33 Correct 358 ms 27140 KB Output is correct
34 Correct 561 ms 36452 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10332 KB Output is correct
3 Correct 2 ms 10332 KB Output is correct
4 Correct 2 ms 10332 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10344 KB Output is correct
7 Correct 2 ms 10328 KB Output is correct
8 Correct 3 ms 10332 KB Output is correct
9 Correct 2 ms 10332 KB Output is correct
10 Correct 2 ms 10356 KB Output is correct
11 Correct 2 ms 10332 KB Output is correct
12 Correct 3 ms 10332 KB Output is correct
13 Correct 2 ms 10332 KB Output is correct
14 Correct 2 ms 10332 KB Output is correct
15 Correct 2 ms 10160 KB Output is correct
16 Correct 2 ms 10332 KB Output is correct
17 Correct 3 ms 10172 KB Output is correct
18 Correct 2 ms 10332 KB Output is correct
19 Correct 2 ms 10332 KB Output is correct
20 Correct 2 ms 10332 KB Output is correct
21 Correct 4 ms 10356 KB Output is correct
22 Correct 3 ms 10332 KB Output is correct
23 Correct 5 ms 10704 KB Output is correct
24 Correct 4 ms 10332 KB Output is correct
25 Correct 3 ms 10332 KB Output is correct
26 Correct 4 ms 10332 KB Output is correct
27 Correct 3 ms 10332 KB Output is correct
28 Correct 3 ms 10352 KB Output is correct
29 Correct 3 ms 10352 KB Output is correct
30 Correct 3 ms 10332 KB Output is correct
31 Correct 3 ms 10468 KB Output is correct
32 Correct 4 ms 10332 KB Output is correct
33 Correct 5 ms 10588 KB Output is correct
34 Correct 3 ms 10332 KB Output is correct
35 Correct 4 ms 10332 KB Output is correct
36 Correct 3 ms 10476 KB Output is correct
37 Correct 4 ms 10380 KB Output is correct
38 Correct 3 ms 10584 KB Output is correct
39 Correct 166 ms 19948 KB Output is correct
40 Correct 160 ms 20184 KB Output is correct
41 Correct 168 ms 20008 KB Output is correct
42 Correct 140 ms 20180 KB Output is correct
43 Correct 210 ms 20424 KB Output is correct
44 Correct 106 ms 19240 KB Output is correct
45 Correct 135 ms 25036 KB Output is correct
46 Correct 80 ms 27508 KB Output is correct
47 Correct 202 ms 26176 KB Output is correct
48 Correct 624 ms 51516 KB Output is correct
49 Correct 612 ms 50304 KB Output is correct
50 Correct 206 ms 26212 KB Output is correct
51 Correct 248 ms 26448 KB Output is correct
52 Correct 222 ms 26484 KB Output is correct
53 Correct 358 ms 27140 KB Output is correct
54 Correct 561 ms 36452 KB Output is correct
55 Correct 17 ms 11356 KB Output is correct
56 Correct 11 ms 11200 KB Output is correct
57 Correct 108 ms 20300 KB Output is correct
58 Correct 46 ms 18356 KB Output is correct
59 Correct 219 ms 30716 KB Output is correct
60 Correct 678 ms 49856 KB Output is correct
61 Correct 273 ms 27820 KB Output is correct
62 Correct 211 ms 26712 KB Output is correct
63 Correct 243 ms 26412 KB Output is correct
64 Correct 684 ms 32188 KB Output is correct
65 Correct 604 ms 37272 KB Output is correct
66 Correct 625 ms 47816 KB Output is correct
67 Correct 92 ms 25212 KB Output is correct
68 Correct 342 ms 35652 KB Output is correct
69 Correct 396 ms 35800 KB Output is correct
70 Correct 323 ms 34784 KB Output is correct