oj.uz

Submission #105922

# Submission time Handle Problem Language Result Execution time Memory
105922 2019-04-15T17:42:55 Z tincamatei Race (IOI11_race) C++14
9 / 100
 208 ms 38616 KB 
#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;

vector<pair<int, int> > graph[MAX_N];
set<pair<long long, int> > chains[MAX_N];
long long lazy[MAX_N];
int lazyedge[MAX_N];
int rez = MAX_N + 1;

int subtree[MAX_N];

void predfs(int nod, int papa = -1) {
	subtree[nod]++;
	for(auto it: graph[nod])
		if(it.first != papa) {
			predfs(it.first, nod);
			subtree[nod] += subtree[it.first];
		}
}

void solvedfs(int nod, int k, int papa = -1) {
	int heavySon = -1;

	for(auto it: graph[nod])
		if(it.first != papa && (heavySon == -1 || (heavySon != -1 && subtree[it.first] > subtree[heavySon])))
			heavySon = it.first;
	
	for(auto it: graph[nod])
		if(it.first != papa) {
			solvedfs(it.first, k, nod);
			lazy[it.first] += it.second;
			lazyedge[it.first]++;
		}
	
	if(heavySon != -1) {
		// Toarna chestii in heavySon
		chains[nod].swap(chains[heavySon]);
		swap(lazy[nod], lazy[heavySon]);
		swap(lazyedge[nod], lazyedge[heavySon]);

		for(auto it: graph[nod])
			if(it.first != papa && it.first != heavySon) {
				for(auto ch: chains[it.first]) {
					set<pair<long long, int> >::iterator lb;
					lb = chains[nod].lower_bound(make_pair(k - (ch.first + lazy[it.first]) - lazy[nod], -MAX_N-1));
					if(lb != chains[nod].end() && lb->first + ch.first + lazy[it.first] + lazy[nod] == k)
						rez = min(rez, ch.second + lb->second + lazyedge[it.first] + lazyedge[nod]);
				}
				
				for(auto ch: chains[it.first]) {
					chains[nod].insert(make_pair(ch.first + lazy[it.first] - lazy[nod], ch.second));
				}
			}
	}

	set<pair<long long, int> >::iterator lb;
	lb = chains[nod].lower_bound(make_pair(k - lazy[nod], -MAX_N-1));
	if(lb != chains[nod].end() && lb->first + lazy[nod] == k)
		rez = min(rez, lb->second + lazyedge[nod]);
	
	chains[nod].insert(make_pair(-lazy[nod], -lazyedge[nod]));
}

int best_path(int N, int K, int H[][2], int L[]) {
  for(int i = 0; i < N - 1; ++i)
		for(int j = 0; j < 2; ++j)
			graph[H[i][j]].push_back(make_pair(H[i][0] ^ H[i][1] ^ H[i][j], L[i]));
	
	predfs(0);
	solvedfs(0, K);

	if(rez == MAX_N + 1)
		return -1;
	return rez;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14592 KB Output is correct
2 Correct 16 ms 14464 KB Output is correct
3 Correct 17 ms 14536 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 17 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 15 ms 14464 KB Output is correct
10 Correct 17 ms 14436 KB Output is correct
11 Correct 16 ms 14464 KB Output is correct
12 Correct 16 ms 14464 KB Output is correct
13 Correct 16 ms 14464 KB Output is correct
14 Correct 17 ms 14592 KB Output is correct
15 Correct 16 ms 14464 KB Output is correct
16 Correct 17 ms 14464 KB Output is correct
17 Correct 17 ms 14464 KB Output is correct
18 Correct 21 ms 14460 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14592 KB Output is correct
2 Correct 16 ms 14464 KB Output is correct
3 Correct 17 ms 14536 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 17 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 15 ms 14464 KB Output is correct
10 Correct 17 ms 14436 KB Output is correct
11 Correct 16 ms 14464 KB Output is correct
12 Correct 16 ms 14464 KB Output is correct
13 Correct 16 ms 14464 KB Output is correct
14 Correct 17 ms 14592 KB Output is correct
15 Correct 16 ms 14464 KB Output is correct
16 Correct 17 ms 14464 KB Output is correct
17 Correct 17 ms 14464 KB Output is correct
18 Correct 21 ms 14460 KB Output is correct
19 Correct 16 ms 14452 KB Output is correct
20 Correct 17 ms 14464 KB Output is correct
21 Incorrect 18 ms 14720 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14592 KB Output is correct
2 Correct 16 ms 14464 KB Output is correct
3 Correct 17 ms 14536 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 17 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 15 ms 14464 KB Output is correct
10 Correct 17 ms 14436 KB Output is correct
11 Correct 16 ms 14464 KB Output is correct
12 Correct 16 ms 14464 KB Output is correct
13 Correct 16 ms 14464 KB Output is correct
14 Correct 17 ms 14592 KB Output is correct
15 Correct 16 ms 14464 KB Output is correct
16 Correct 17 ms 14464 KB Output is correct
17 Correct 17 ms 14464 KB Output is correct
18 Correct 21 ms 14460 KB Output is correct
19 Incorrect 208 ms 38616 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 14592 KB Output is correct
2 Correct 16 ms 14464 KB Output is correct
3 Correct 17 ms 14536 KB Output is correct
4 Correct 16 ms 14464 KB Output is correct
5 Correct 15 ms 14464 KB Output is correct
6 Correct 17 ms 14464 KB Output is correct
7 Correct 16 ms 14464 KB Output is correct
8 Correct 16 ms 14464 KB Output is correct
9 Correct 15 ms 14464 KB Output is correct
10 Correct 17 ms 14436 KB Output is correct
11 Correct 16 ms 14464 KB Output is correct
12 Correct 16 ms 14464 KB Output is correct
13 Correct 16 ms 14464 KB Output is correct
14 Correct 17 ms 14592 KB Output is correct
15 Correct 16 ms 14464 KB Output is correct
16 Correct 17 ms 14464 KB Output is correct
17 Correct 17 ms 14464 KB Output is correct
18 Correct 21 ms 14460 KB Output is correct
19 Correct 16 ms 14452 KB Output is correct
20 Correct 17 ms 14464 KB Output is correct
21 Incorrect 18 ms 14720 KB Output isn't correct
22 Halted 0 ms 0 KB -