oj.uz

Submission #139436

# Submission time Handle Problem Language Result Execution time Memory
139436 2019-07-31T17:18:42 Z claudy Race (IOI11_race) C++14
100 / 100
 1788 ms 139276 KB 
# include "race.h"
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;

int dep[1 << 18],dep2[1 << 18],s[1 << 18],x,ans = 1e18,n,k;
vector<pair<int,int>>vec[1 << 18];
unordered_map<int,multiset<int>>ms;

inline void pre(int nod,int par,int val)
{
	dep[nod] = dep[par] + val;
	dep2[nod] = dep2[par] + 1;
	s[nod] = 1;
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			pre(it.first,nod,it.second);
			s[nod] += s[it.first];
		}
	}
}

inline void add1_node(int nod,int gg)
{
	if(sz(ms[2 * gg + k - dep[nod]]))
	{
		x = min(x,dep2[nod] + *(ms[2 * gg + k - dep[nod]].begin()));
	}
}

inline void add2_node(int nod,int gg)
{
	ms[dep[nod]].insert(dep2[nod]);
}

inline void add1(int nod,int par,int gg)
{
	add1_node(nod,gg);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			add1(it.first,nod,gg);
		}
	}
}

inline void add2(int nod,int par,int gg)
{
	add2_node(nod,gg);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			add2(it.first,nod,gg);
		}
	}
}



inline void del_node(int nod)
{
	ms[dep[nod]].erase(ms[dep[nod]].find(dep2[nod]));
}

inline void del(int nod,int par)
{
	del_node(nod);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			del(it.first,nod);
		}
	}
}

inline void dfs(int nod,int par,bool keep)
{
	pair<int,int>mx = mp(-1,-1);
	for(auto it : vec[nod])
	{
		if(it.first != par)
		{
			mx = max(mx,mp(s[it.first],it.first));
		}
	}
	for(auto it : vec[nod])
	{
		if(it.first != par && it.first != mx.second)
		{
			dfs(it.first,nod,0);
		}
	}
	if(mx.second != -1) dfs(mx.second,nod,1);
	x = 1e18;
	add1_node(nod,dep[nod]);
	add2_node(nod,dep[nod]);
	for(auto it : vec[nod])
	{
		if(it.first != par && it.first != mx.second)
		{
			add1(it.first,nod,dep[nod]);
			add2(it.first,nod,dep[nod]);
		}
	}
	//cout << nod << ' ' << x << ' ' << x - 2 * dep2[nod] << '\n';
	if(x != 1e18) ans = min(ans,x - 2 * dep2[nod]);
	if(keep) return ;
	del(nod,par);
}

# undef int 
int best_path(int N, int K, int H[][2], int L[])
{
# define int ll
	k = K;
	n = N;
	for(int i = 0;i < n - 1;i++)
	{
		vec[H[i][0]].pb(mp(H[i][1],L[i]));
		vec[H[i][1]].pb(mp(H[i][0],L[i]));
	}
	pre(0,0,0);
	dfs(0,0,1);
	if(ans == 1e18) return -1;
	else return ans;
}

Compilation message

race.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6520 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 8 ms 6648 KB Output is correct
4 Correct 8 ms 6520 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6520 KB Output is correct
7 Correct 8 ms 6620 KB Output is correct
8 Correct 8 ms 6520 KB Output is correct
9 Correct 8 ms 6620 KB Output is correct
10 Correct 9 ms 6692 KB Output is correct
11 Correct 8 ms 6620 KB Output is correct
12 Correct 8 ms 6524 KB Output is correct
13 Correct 8 ms 6640 KB Output is correct
14 Correct 8 ms 6520 KB Output is correct
15 Correct 8 ms 6648 KB Output is correct
16 Correct 8 ms 6648 KB Output is correct
17 Correct 8 ms 6612 KB Output is correct
18 Correct 8 ms 6492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6520 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 8 ms 6648 KB Output is correct
4 Correct 8 ms 6520 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6520 KB Output is correct
7 Correct 8 ms 6620 KB Output is correct
8 Correct 8 ms 6520 KB Output is correct
9 Correct 8 ms 6620 KB Output is correct
10 Correct 9 ms 6692 KB Output is correct
11 Correct 8 ms 6620 KB Output is correct
12 Correct 8 ms 6524 KB Output is correct
13 Correct 8 ms 6640 KB Output is correct
14 Correct 8 ms 6520 KB Output is correct
15 Correct 8 ms 6648 KB Output is correct
16 Correct 8 ms 6648 KB Output is correct
17 Correct 8 ms 6612 KB Output is correct
18 Correct 8 ms 6492 KB Output is correct
19 Correct 8 ms 6520 KB Output is correct
20 Correct 8 ms 6520 KB Output is correct
21 Correct 9 ms 6776 KB Output is correct
22 Correct 10 ms 7032 KB Output is correct
23 Correct 10 ms 7032 KB Output is correct
24 Correct 10 ms 7032 KB Output is correct
25 Correct 10 ms 7032 KB Output is correct
26 Correct 10 ms 7032 KB Output is correct
27 Correct 9 ms 6648 KB Output is correct
28 Correct 10 ms 7032 KB Output is correct
29 Correct 10 ms 7032 KB Output is correct
30 Correct 10 ms 6964 KB Output is correct
31 Correct 10 ms 7036 KB Output is correct
32 Correct 10 ms 7032 KB Output is correct
33 Correct 10 ms 7032 KB Output is correct
34 Correct 10 ms 6904 KB Output is correct
35 Correct 9 ms 6904 KB Output is correct
36 Correct 11 ms 6904 KB Output is correct
37 Correct 11 ms 6904 KB Output is correct
38 Correct 10 ms 6948 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6520 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 8 ms 6648 KB Output is correct
4 Correct 8 ms 6520 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6520 KB Output is correct
7 Correct 8 ms 6620 KB Output is correct
8 Correct 8 ms 6520 KB Output is correct
9 Correct 8 ms 6620 KB Output is correct
10 Correct 9 ms 6692 KB Output is correct
11 Correct 8 ms 6620 KB Output is correct
12 Correct 8 ms 6524 KB Output is correct
13 Correct 8 ms 6640 KB Output is correct
14 Correct 8 ms 6520 KB Output is correct
15 Correct 8 ms 6648 KB Output is correct
16 Correct 8 ms 6648 KB Output is correct
17 Correct 8 ms 6612 KB Output is correct
18 Correct 8 ms 6492 KB Output is correct
19 Correct 368 ms 20216 KB Output is correct
20 Correct 369 ms 20252 KB Output is correct
21 Correct 371 ms 20312 KB Output is correct
22 Correct 323 ms 20472 KB Output is correct
23 Correct 341 ms 20728 KB Output is correct
24 Correct 238 ms 19832 KB Output is correct
25 Correct 154 ms 37300 KB Output is correct
26 Correct 102 ms 51064 KB Output is correct
27 Correct 347 ms 34872 KB Output is correct
28 Correct 527 ms 130156 KB Output is correct
29 Correct 549 ms 126596 KB Output is correct
30 Correct 369 ms 35072 KB Output is correct
31 Correct 406 ms 34968 KB Output is correct
32 Correct 472 ms 35444 KB Output is correct
33 Correct 572 ms 34168 KB Output is correct
34 Correct 1574 ms 125080 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6520 KB Output is correct
2 Correct 8 ms 6648 KB Output is correct
3 Correct 8 ms 6648 KB Output is correct
4 Correct 8 ms 6520 KB Output is correct
5 Correct 8 ms 6648 KB Output is correct
6 Correct 8 ms 6520 KB Output is correct
7 Correct 8 ms 6620 KB Output is correct
8 Correct 8 ms 6520 KB Output is correct
9 Correct 8 ms 6620 KB Output is correct
10 Correct 9 ms 6692 KB Output is correct
11 Correct 8 ms 6620 KB Output is correct
12 Correct 8 ms 6524 KB Output is correct
13 Correct 8 ms 6640 KB Output is correct
14 Correct 8 ms 6520 KB Output is correct
15 Correct 8 ms 6648 KB Output is correct
16 Correct 8 ms 6648 KB Output is correct
17 Correct 8 ms 6612 KB Output is correct
18 Correct 8 ms 6492 KB Output is correct
19 Correct 8 ms 6520 KB Output is correct
20 Correct 8 ms 6520 KB Output is correct
21 Correct 9 ms 6776 KB Output is correct
22 Correct 10 ms 7032 KB Output is correct
23 Correct 10 ms 7032 KB Output is correct
24 Correct 10 ms 7032 KB Output is correct
25 Correct 10 ms 7032 KB Output is correct
26 Correct 10 ms 7032 KB Output is correct
27 Correct 9 ms 6648 KB Output is correct
28 Correct 10 ms 7032 KB Output is correct
29 Correct 10 ms 7032 KB Output is correct
30 Correct 10 ms 6964 KB Output is correct
31 Correct 10 ms 7036 KB Output is correct
32 Correct 10 ms 7032 KB Output is correct
33 Correct 10 ms 7032 KB Output is correct
34 Correct 10 ms 6904 KB Output is correct
35 Correct 9 ms 6904 KB Output is correct
36 Correct 11 ms 6904 KB Output is correct
37 Correct 11 ms 6904 KB Output is correct
38 Correct 10 ms 6948 KB Output is correct
39 Correct 368 ms 20216 KB Output is correct
40 Correct 369 ms 20252 KB Output is correct
41 Correct 371 ms 20312 KB Output is correct
42 Correct 323 ms 20472 KB Output is correct
43 Correct 341 ms 20728 KB Output is correct
44 Correct 238 ms 19832 KB Output is correct
45 Correct 154 ms 37300 KB Output is correct
46 Correct 102 ms 51064 KB Output is correct
47 Correct 347 ms 34872 KB Output is correct
48 Correct 527 ms 130156 KB Output is correct
49 Correct 549 ms 126596 KB Output is correct
50 Correct 369 ms 35072 KB Output is correct
51 Correct 406 ms 34968 KB Output is correct
52 Correct 472 ms 35444 KB Output is correct
53 Correct 572 ms 34168 KB Output is correct
54 Correct 1574 ms 125080 KB Output is correct
55 Correct 27 ms 9336 KB Output is correct
56 Correct 27 ms 7928 KB Output is correct
57 Correct 304 ms 20804 KB Output is correct
58 Correct 102 ms 20100 KB Output is correct
59 Correct 157 ms 68408 KB Output is correct
60 Correct 536 ms 127392 KB Output is correct
61 Correct 410 ms 39944 KB Output is correct
62 Correct 371 ms 35192 KB Output is correct
63 Correct 491 ms 35320 KB Output is correct
64 Correct 1379 ms 76836 KB Output is correct
65 Correct 1788 ms 139276 KB Output is correct
66 Correct 764 ms 126068 KB Output is correct
67 Correct 350 ms 36188 KB Output is correct
68 Correct 1016 ms 89320 KB Output is correct
69 Correct 1040 ms 90088 KB Output is correct
70 Correct 968 ms 86380 KB Output is correct