oj.uz

Submission #397947

# Submission time Handle Problem Language Result Execution time Memory
397947 2021-05-03T12:23:31 Z keta_tsimakuridze Factories (JOI14_factories) C++14
100 / 100
 5218 ms 180996 KB 
#include "factories.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int NN=5e5+5;
const long long Inf=1e15;
int sz[NN],par[NN],H[NN],fix[NN];
long long dist[NN][20],mn[NN];
vector<pair<int,int> >V[NN];
void get_sz(int u,int p){
	sz[u] = 1;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i].f!=p && !fix[V[u][i].f]) get_sz(V[u][i].f,u),sz[u]+=sz[V[u][i].f];
	}
}
int find_centroid(int u,int p,int Sz){
	for(int i=0;i<V[u].size();i++){
		if(V[u][i].f==p || fix[V[u][i].f]) continue;
		if(sz[V[u][i].f] > Sz/2) return find_centroid(V[u][i].f,u,Sz);
	}
	return u;
}
void dfs(int u,int p,int h){
	for(int i=0;i<V[u].size();i++){
		if(V[u][i].f==p || fix[V[u][i].f]) continue;	
		dist[V[u][i].f][h] = dist[u][h] + V[u][i].s;	
		dfs(V[u][i].f,u,h);
	}
}
void centroid_decomp(int u,int p,int h){
	get_sz(u,0); 
	int c = find_centroid(u,0,sz[u]);
	par[c] = p;
	H[c] = h;
	mn[c] =Inf;
	dfs(c,0,h);
	fix[c] = 1;
	for(int i=0;i<V[c].size();i++){
		if(!fix[V[c][i].f]) centroid_decomp(V[c][i].f,c,h+1);
	}
}
void Init(int N, int A[], int B[], int D[]) {
	for(int i=0;i<N-1;i++){
		A[i]++;
		B[i]++;
		V[A[i]].push_back({B[i],D[i]});
		V[B[i]].push_back({A[i],D[i]});
	}
	centroid_decomp(1,0,0);
}

long long Query(int S, int X[], int T, int Y[]) {
	
	vector<int> remove;
	for(int i=0;i<S;i++){
		X[i]++;
		int c = X[i]; 
		while(c!=0){
			if(mn[c] == Inf)remove.push_back(c);
			mn[c] = min(mn[c],dist[X[i]][H[c]]);
			c=par[c];
		}
	}
	long long ans = Inf;
	for(int i =0;i<T;i++){
		Y[i]++;
		int c = Y[i];
		while(c!=0){
			ans = min(mn[c] + dist[Y[i]][H[c]],ans);
			c=par[c];
		}		
	}
	for(int i=0;i<remove.size();i++){
		mn[remove[i]]=Inf;
	}
  return ans;
}

Compilation message

factories.cpp: In function 'void get_sz(int, int)':
factories.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'int find_centroid(int, int, int)':
factories.cpp:18:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void dfs(int, int, int)':
factories.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void centroid_decomp(int, int, int)':
factories.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<V[c].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:74:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i=0;i<remove.size();i++){
      |              ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12492 KB Output is correct
2 Correct 358 ms 21416 KB Output is correct
3 Correct 435 ms 30792 KB Output is correct
4 Correct 393 ms 30788 KB Output is correct
5 Correct 442 ms 30900 KB Output is correct
6 Correct 271 ms 30668 KB Output is correct
7 Correct 399 ms 30748 KB Output is correct
8 Correct 405 ms 30756 KB Output is correct
9 Correct 415 ms 30916 KB Output is correct
10 Correct 284 ms 30660 KB Output is correct
11 Correct 401 ms 30688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12236 KB Output is correct
2 Correct 2239 ms 152336 KB Output is correct
3 Correct 3333 ms 152996 KB Output is correct
4 Correct 864 ms 152588 KB Output is correct
5 Correct 4408 ms 176416 KB Output is correct
6 Correct 3468 ms 155236 KB Output is correct
7 Correct 1088 ms 58584 KB Output is correct
8 Correct 506 ms 59372 KB Output is correct
9 Correct 1235 ms 62908 KB Output is correct
10 Correct 1064 ms 59952 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12492 KB Output is correct
2 Correct 358 ms 21416 KB Output is correct
3 Correct 435 ms 30792 KB Output is correct
4 Correct 393 ms 30788 KB Output is correct
5 Correct 442 ms 30900 KB Output is correct
6 Correct 271 ms 30668 KB Output is correct
7 Correct 399 ms 30748 KB Output is correct
8 Correct 405 ms 30756 KB Output is correct
9 Correct 415 ms 30916 KB Output is correct
10 Correct 284 ms 30660 KB Output is correct
11 Correct 401 ms 30688 KB Output is correct
12 Correct 9 ms 12236 KB Output is correct
13 Correct 2239 ms 152336 KB Output is correct
14 Correct 3333 ms 152996 KB Output is correct
15 Correct 864 ms 152588 KB Output is correct
16 Correct 4408 ms 176416 KB Output is correct
17 Correct 3468 ms 155236 KB Output is correct
18 Correct 1088 ms 58584 KB Output is correct
19 Correct 506 ms 59372 KB Output is correct
20 Correct 1235 ms 62908 KB Output is correct
21 Correct 1064 ms 59952 KB Output is correct
22 Correct 2528 ms 160088 KB Output is correct
23 Correct 2692 ms 163092 KB Output is correct
24 Correct 3838 ms 162384 KB Output is correct
25 Correct 3967 ms 165668 KB Output is correct
26 Correct 3801 ms 161424 KB Output is correct
27 Correct 5218 ms 180996 KB Output is correct
28 Correct 1100 ms 163444 KB Output is correct
29 Correct 3991 ms 161196 KB Output is correct
30 Correct 3779 ms 160644 KB Output is correct
31 Correct 3942 ms 161260 KB Output is correct
32 Correct 1157 ms 63576 KB Output is correct
33 Correct 515 ms 60248 KB Output is correct
34 Correct 759 ms 56560 KB Output is correct
35 Correct 772 ms 56468 KB Output is correct
36 Correct 955 ms 57080 KB Output is correct
37 Correct 984 ms 57124 KB Output is correct