oj.uz

Submission #673406

# Submission time Handle Problem Language Result Execution time Memory
673406 2022-12-20T13:59:20 Z dsyz Factories (JOI14_factories) C++17
100 / 100
 4189 ms 292056 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
vector<pair<ll,ll> > v[MAXN];
ll sub[MAXN];
ll par[MAXN];
ll lvl[MAXN];
ll dist[MAXN][20];
ll m[MAXN];
ll dfs1(ll x,ll p,ll l){
	sub[x] = 1;
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1){ //unvisited
			sub[x] += dfs1(u.first,x,l);
		}
	}
	return sub[x];
}
ll dfs2(ll x,ll p,ll siz){ //siz is total size of this centroid tree 
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1 && sub[u.first] > siz / 2){
			return dfs2(u.first,x,siz); //remember that siz remains constant
		}
	}
	return x;
}
void dfsdist(ll x,ll p,ll curlvl,ll curdist){
	dist[x][curlvl] = curdist;
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1){ //unvisited
			dfsdist(u.first,x,curlvl,curdist + u.second);
			//Note: curlvl is unchanged since we are moving down so
			//the relative lvl has already changed
		}
	}
}
void build(ll x,ll p,ll l){
	ll siz = dfs1(x,p,l);
	ll cent = dfs2(x,p,siz);
	if(p == -1) p = cent;
	par[cent] = p;
	lvl[cent] = l;
	dfsdist(cent,-1,l,0);
	for(auto u : v[cent]){
		if(lvl[u.first] == -1){ //unvisited
			build(u.first,cent,l + 1);
		}
	}
}

void Init(int N, int A[], int B[], int D[]) {
	for(ll i = 0;i < N - 1;i++){
		v[A[i]].push_back(make_pair(B[i],D[i]));
		v[B[i]].push_back(make_pair(A[i],D[i]));
	}
	for(ll i = 0;i < MAXN;i++){
		for(ll j = 0;j < 20;j++){
			dist[i][j] = 1e18;
		}
	}
	memset(lvl,-1,sizeof(lvl)); //need lvl to find dist[i][lvl]
	build(0,-1,0);
	for(ll i = 0;i < MAXN;i++){
		m[i] = 1e18;
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	for(ll i = 0;i < S;i++){
		ll curlevel = lvl[X[i]];
		ll x = X[i];
		while(curlevel >= 0){
			m[x] = min(m[x],dist[X[i]][curlevel]);
			x = par[x];
			curlevel--;
		}
	}
	ll ans = 1e18;
	for(ll i = 0;i < T;i++){
		ll curlevel = lvl[Y[i]];
		ll y = Y[i];
		while(curlevel >= 0){
			ans = min(ans,m[y] + dist[Y[i]][curlevel]);
			y = par[y];
			curlevel--;
		}
	}
	for(ll i = 0;i < S;i++){ //undo, prepare for next query
		ll curlevel = lvl[X[i]];
		ll x = X[i];
		while(curlevel >= 0){
			m[x] = 1e18;
			x = par[x];
			curlevel--;
		}
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 196452 KB Output is correct
2 Correct 313 ms 213912 KB Output is correct
3 Correct 320 ms 213832 KB Output is correct
4 Correct 360 ms 213888 KB Output is correct
5 Correct 351 ms 214160 KB Output is correct
6 Correct 269 ms 213916 KB Output is correct
7 Correct 345 ms 213932 KB Output is correct
8 Correct 318 ms 214012 KB Output is correct
9 Correct 338 ms 214096 KB Output is correct
10 Correct 259 ms 213784 KB Output is correct
11 Correct 339 ms 213836 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 196072 KB Output is correct
2 Correct 1641 ms 261020 KB Output is correct
3 Correct 2643 ms 263212 KB Output is correct
4 Correct 654 ms 258192 KB Output is correct
5 Correct 3541 ms 288660 KB Output is correct
6 Correct 2712 ms 265384 KB Output is correct
7 Correct 874 ms 227800 KB Output is correct
8 Correct 392 ms 227760 KB Output is correct
9 Correct 980 ms 231984 KB Output is correct
10 Correct 823 ms 229252 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 196452 KB Output is correct
2 Correct 313 ms 213912 KB Output is correct
3 Correct 320 ms 213832 KB Output is correct
4 Correct 360 ms 213888 KB Output is correct
5 Correct 351 ms 214160 KB Output is correct
6 Correct 269 ms 213916 KB Output is correct
7 Correct 345 ms 213932 KB Output is correct
8 Correct 318 ms 214012 KB Output is correct
9 Correct 338 ms 214096 KB Output is correct
10 Correct 259 ms 213784 KB Output is correct
11 Correct 339 ms 213836 KB Output is correct
12 Correct 81 ms 196072 KB Output is correct
13 Correct 1641 ms 261020 KB Output is correct
14 Correct 2643 ms 263212 KB Output is correct
15 Correct 654 ms 258192 KB Output is correct
16 Correct 3541 ms 288660 KB Output is correct
17 Correct 2712 ms 265384 KB Output is correct
18 Correct 874 ms 227800 KB Output is correct
19 Correct 392 ms 227760 KB Output is correct
20 Correct 980 ms 231984 KB Output is correct
21 Correct 823 ms 229252 KB Output is correct
22 Correct 2110 ms 268092 KB Output is correct
23 Correct 2254 ms 270660 KB Output is correct
24 Correct 3428 ms 271416 KB Output is correct
25 Correct 3308 ms 274968 KB Output is correct
26 Correct 3328 ms 271164 KB Output is correct
27 Correct 4189 ms 292056 KB Output is correct
28 Correct 837 ms 268648 KB Output is correct
29 Correct 3204 ms 270964 KB Output is correct
30 Correct 3178 ms 270604 KB Output is correct
31 Correct 3194 ms 271124 KB Output is correct
32 Correct 964 ms 232692 KB Output is correct
33 Correct 428 ms 228068 KB Output is correct
34 Correct 677 ms 225360 KB Output is correct
35 Correct 643 ms 225312 KB Output is correct
36 Correct 837 ms 226116 KB Output is correct
37 Correct 824 ms 226160 KB Output is correct