oj.uz

Submission #585970

# Submission time Handle Problem Language Result Execution time Memory
585970 2022-06-29T15:46:01 Z M_W Race (IOI11_race) C++17
0 / 100
 60 ms 12836 KB 
#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int bk[1000002], mn[1000002];
bool blocked[200001];
vector<ii> adj[200001];
int sz[200001], book = 1;
int ans = 1e9, K;

// Centroid

void dfs(int a, int p){
	sz[a] = 1;
	for(auto [x, w] : adj[a]){
		if(blocked[x] || x == p) continue;
		dfs(x, a);
		sz[a] += sz[x];
	}
}

void dfs_upd(int a, int p, long long wt, int ed){
	for(auto [x, w] : adj[a]){
		if(blocked[x] || x == p) continue;
		
		int idx = int(min(1000001 * 1ll, wt + w));
		bk[idx] = book; mn[idx] = mn[idx] == 0 ? ed : min(mn[idx], ed);
		dfs_upd(x, a, wt + w, ed + 1);
	}
}

void dfs_path(int a, int p, long long wt, int ed){
	for(auto [x, w] : adj[a]){
		if(blocked[x] || x == p) continue;
		
		int idx = int(min(1000001 * 1ll, wt + w));
		if(K - idx >= 0){
			if(bk[K - idx] < book && bk[K - idx]) ans = min(ans, ed + mn[K - idx]);
		}
		dfs_path(x, a, wt + w, ed + 1);
		
		
		if(ed == 1){
			bk[idx] = book; mn[idx] = mn[idx] == 0 ? ed : min(mn[idx], ed);
			dfs_upd(x, a, wt + w, ed + 1);
		} 
		
		book++;
	}
}

void dec(int a, int p){
	dfs(a, a);
	int cur = a, prev = -1;
	while(true){
		int mx = -1, nxt;
		for(auto [x, w] : adj[cur]){
			if(blocked[x] || x == prev) continue;
			if(sz[x] > mx){
				mx = sz[x];
				nxt = x;
			}
		}
		if(mx * 2 > sz[a]){
			prev = cur;
			cur = nxt;
		}
		else break;
	}
	blocked[cur] = true;
	book = 1;
	dfs_path(cur, cur, 0, 1);
	
	memset(bk, 0, sizeof bk);
	memset(mn, 0, sizeof mn);
	for(auto [x, w]: adj[cur]) if(!blocked[x]) dec(x, cur);
}

int best_path(int N, int K_tmp, int H[][2], int L[])
{
	K = K_tmp;
	for(int i = 0; i < N - 1; i++){
		adj[H[i][0]].push_back({H[i][1], L[i] * 1ll});
		adj[H[i][1]].push_back({H[i][0], L[i] * 1ll});
	}
	dec(0, -1);
	return ans == 1000000000 ? -1 : ans;
}

Compilation message

race.cpp: In function 'void dec(int, int)':
race.cpp:55:16: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |   int mx = -1, nxt;
      |                ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12836 KB Output is correct
2 Correct 48 ms 12756 KB Output is correct
3 Correct 56 ms 12816 KB Output is correct
4 Correct 49 ms 12836 KB Output is correct
5 Correct 60 ms 12836 KB Output is correct
6 Correct 49 ms 12756 KB Output is correct
7 Correct 52 ms 12820 KB Output is correct
8 Incorrect 59 ms 12756 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12836 KB Output is correct
2 Correct 48 ms 12756 KB Output is correct
3 Correct 56 ms 12816 KB Output is correct
4 Correct 49 ms 12836 KB Output is correct
5 Correct 60 ms 12836 KB Output is correct
6 Correct 49 ms 12756 KB Output is correct
7 Correct 52 ms 12820 KB Output is correct
8 Incorrect 59 ms 12756 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12836 KB Output is correct
2 Correct 48 ms 12756 KB Output is correct
3 Correct 56 ms 12816 KB Output is correct
4 Correct 49 ms 12836 KB Output is correct
5 Correct 60 ms 12836 KB Output is correct
6 Correct 49 ms 12756 KB Output is correct
7 Correct 52 ms 12820 KB Output is correct
8 Incorrect 59 ms 12756 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12836 KB Output is correct
2 Correct 48 ms 12756 KB Output is correct
3 Correct 56 ms 12816 KB Output is correct
4 Correct 49 ms 12836 KB Output is correct
5 Correct 60 ms 12836 KB Output is correct
6 Correct 49 ms 12756 KB Output is correct
7 Correct 52 ms 12820 KB Output is correct
8 Incorrect 59 ms 12756 KB Output isn't correct
9 Halted 0 ms 0 KB -