oj.uz

Submission #982453

# Submission time Handle Problem Language Result Execution time Memory
982453 2024-05-14T09:22:42 Z Amaarsaa Factories (JOI14_factories) C++14
100 / 100
 3760 ms 381144 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
using namespace std;
#define M 500005
 
pair<int, ll> d[M];
 
bool act[M];
vector<pair<int, ll> > cen[M], adj[M];
 
void dfs3(int root, int v, int p = -1, ll d = 0){
	cen[v].push_back({root, d});
	for(auto& x : adj[v]){
		int u = x.ff;
		if(!act[u] && p != u)
			dfs3(root, u, v, d + x.ss);
	}
}
 
int q = M;
int sz[M];
 
void dfs1(int v, int p = -1){
	sz[v] = 1;
	for(auto& x : adj[v]){
		int u = x.ff;
		if(!act[u] && p != u){
			dfs1(u, v);
			sz[v] += sz[u];
		}
	}
}
 
int dfs2(int v, int p, int s){
	for(auto& x : adj[v]){
		int u = x.ff;
		if(!act[u] && p != u)
			if(sz[u] > s)
				return dfs2(u, v, s);
	}
	return v;
}
 
void decomp(int v){
	dfs1(v);
	v = dfs2(v, -1, sz[v] / 2);
	dfs3(v, v);
	act[v] = 1;
	for(auto& x : adj[v])
		if(!act[x.ff])
			decomp(x.ff);
}
 
void Init(int N, int A[], int B[], int D[]) {
	for(int i = 0; i < N; i++)
		d[i] = {q, 0};
	
	for(int i = 0; i < N - 1; i++){
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
 
	decomp(0);
}
 
long long Query(int S, int X[], int T, int Y[]) {
	--q;
	ll res = 0x3f3f3f3f3f3f3f3f;
	for(int i = 0; i < S; i++){
		for(auto& x : cen[X[i]]){
			d[x.ff] = min(d[x.ff], {q, x.ss});
		}
	}
	for(int i = 0; i < T; i++)
		for(auto& x : cen[Y[i]])
			if(d[x.ff].ff == q)
				res = min(res, d[x.ff].ss + x.ss);
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45660 KB Output is correct
2 Correct 211 ms 60148 KB Output is correct
3 Correct 223 ms 60500 KB Output is correct
4 Correct 217 ms 60500 KB Output is correct
5 Correct 232 ms 61184 KB Output is correct
6 Correct 146 ms 59636 KB Output is correct
7 Correct 221 ms 60672 KB Output is correct
8 Correct 225 ms 60752 KB Output is correct
9 Correct 236 ms 61396 KB Output is correct
10 Correct 196 ms 59772 KB Output is correct
11 Correct 220 ms 60532 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45656 KB Output is correct
2 Correct 1866 ms 228736 KB Output is correct
3 Correct 3113 ms 300876 KB Output is correct
4 Correct 627 ms 122616 KB Output is correct
5 Correct 3655 ms 381144 KB Output is correct
6 Correct 2861 ms 301088 KB Output is correct
7 Correct 802 ms 100036 KB Output is correct
8 Correct 236 ms 75992 KB Output is correct
9 Correct 830 ms 113048 KB Output is correct
10 Correct 767 ms 100428 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 45660 KB Output is correct
2 Correct 211 ms 60148 KB Output is correct
3 Correct 223 ms 60500 KB Output is correct
4 Correct 217 ms 60500 KB Output is correct
5 Correct 232 ms 61184 KB Output is correct
6 Correct 146 ms 59636 KB Output is correct
7 Correct 221 ms 60672 KB Output is correct
8 Correct 225 ms 60752 KB Output is correct
9 Correct 236 ms 61396 KB Output is correct
10 Correct 196 ms 59772 KB Output is correct
11 Correct 220 ms 60532 KB Output is correct
12 Correct 9 ms 45656 KB Output is correct
13 Correct 1866 ms 228736 KB Output is correct
14 Correct 3113 ms 300876 KB Output is correct
15 Correct 627 ms 122616 KB Output is correct
16 Correct 3655 ms 381144 KB Output is correct
17 Correct 2861 ms 301088 KB Output is correct
18 Correct 802 ms 100036 KB Output is correct
19 Correct 236 ms 75992 KB Output is correct
20 Correct 830 ms 113048 KB Output is correct
21 Correct 767 ms 100428 KB Output is correct
22 Correct 2118 ms 231712 KB Output is correct
23 Correct 2146 ms 235488 KB Output is correct
24 Correct 3182 ms 304780 KB Output is correct
25 Correct 3142 ms 307568 KB Output is correct
26 Correct 3189 ms 306348 KB Output is correct
27 Correct 3760 ms 379988 KB Output is correct
28 Correct 743 ms 129244 KB Output is correct
29 Correct 3089 ms 305236 KB Output is correct
30 Correct 3115 ms 305200 KB Output is correct
31 Correct 3183 ms 305544 KB Output is correct
32 Correct 868 ms 113200 KB Output is correct
33 Correct 229 ms 76220 KB Output is correct
34 Correct 565 ms 93268 KB Output is correct
35 Correct 613 ms 94032 KB Output is correct
36 Correct 767 ms 98896 KB Output is correct
37 Correct 720 ms 98896 KB Output is correct