oj.uz

Submission #1054080

# Submission time Handle Problem Language Result Execution time Memory
1054080 2024-08-12T06:00:53 Z tamir1 Factories (JOI14_factories) C++17
100 / 100
 5089 ms 152880 KB 
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
const ll INF=1e18;
ll dis[500001],c[500001];
int jump[21][500001],dep[500001],par[500001],sz[500001],n;
vector<pair<int,ll>> v[500001];
queue<int> q;
bitset<500001> ok; 
void dfs(int x,int y){
	int nx;
	ll len;
	jump[0][x]=y;
	for(int i=0;i<v[x].size();i++){
		nx=v[x][i].ff;
		if(nx==y) continue;
		len=v[x][i].ss;
		dep[nx]=dep[x]+1;
		dis[nx]=dis[x]+len;
		dfs(nx,x);
	}
}
int up(int x,int k){
	for(int i=0;i<=20;i++){
		if(k&(1<<i)) x=jump[i][x];
	}
	return x;
}
int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	y=up(y,dep[y]-dep[x]);
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(jump[i][x]!=jump[i][y]){
			x=jump[i][x];
			y=jump[i][y];
		}
	}
	return jump[0][x];
}
ll dist(int x,int y){
	return dis[x]+dis[y]-dis[lca(x,y)]*2;
}
int sze(int x,int y){
	sz[x]=1;
	for(int i=0;i<v[x].size();i++){
		int z=v[x][i].ff;
		if(z==y || ok[z]) continue;
		sz[x]+=sze(z,x);
	}
	return sz[x];
}
int centroid(int x,int y,int n){
	for(int i=0;i<v[x].size();i++){
		int z=v[x][i].ff;
		if(z==y || ok[z]) continue;
		if(sz[z]>n/2) return centroid(z,x,n);
	}
	return x;
}
void build(int x,int y){
	int cnt=centroid(x,y,sze(x,y));
	ok[cnt]=1;
	par[cnt]=y;
	for(int i=0;i<v[cnt].size();i++){
		int z=v[cnt][i].ff;
		if(!ok[z]) build(z,cnt);
	}
}
void Init(int N, int A[], int B[], int D[]) {
	n=N;
	for(int i=0;i<N-1;i++){
		v[A[i]].push_back({B[i],D[i]});
		v[B[i]].push_back({A[i],D[i]});
	}
	dfs(0,0);
	for(int j=1;j<=20;j++){
		for(int i=0;i<N;i++){
			jump[j][i]=jump[j-1][jump[j-1][i]];
		}
	}
	build(0,-1);
	for(int i=0;i<N;i++) c[i]=INF;
}
long long Query(int S, int X[], int T, int Y[]) {
	ll res=INF;
	for(int i=0;i<S;i++){
		int x=X[i],y;
		y=x;
		while(y!=-1){
			c[y]=min(c[y],dist(x,y));
			q.push(y);
			y=par[y];
		}
	}
	for(int i=0;i<T;i++){
		int x=Y[i],y;
		y=x;
		while(y!=-1){
			res=min(res,dist(x,y)+c[y]);
			y=par[y];
		}
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		c[x]=INF;
	}
	return res;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'int sze(int, int)':
factories.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
factories.cpp: In function 'void build(int, int)':
factories.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=0;i<v[cnt].size();i++){
      |              ~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 76632 KB Output is correct
2 Correct 453 ms 85844 KB Output is correct
3 Correct 918 ms 85840 KB Output is correct
4 Correct 876 ms 85840 KB Output is correct
5 Correct 969 ms 86096 KB Output is correct
6 Correct 181 ms 85700 KB Output is correct
7 Correct 954 ms 85824 KB Output is correct
8 Correct 933 ms 85848 KB Output is correct
9 Correct 969 ms 86360 KB Output is correct
10 Correct 166 ms 85960 KB Output is correct
11 Correct 884 ms 85820 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 76380 KB Output is correct
2 Correct 1117 ms 125592 KB Output is correct
3 Correct 2542 ms 129312 KB Output is correct
4 Correct 306 ms 123308 KB Output is correct
5 Correct 3428 ms 152880 KB Output is correct
6 Correct 3002 ms 129664 KB Output is correct
7 Correct 2263 ms 95452 KB Output is correct
8 Correct 253 ms 94496 KB Output is correct
9 Correct 2122 ms 98416 KB Output is correct
10 Correct 2299 ms 95864 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 76632 KB Output is correct
2 Correct 453 ms 85844 KB Output is correct
3 Correct 918 ms 85840 KB Output is correct
4 Correct 876 ms 85840 KB Output is correct
5 Correct 969 ms 86096 KB Output is correct
6 Correct 181 ms 85700 KB Output is correct
7 Correct 954 ms 85824 KB Output is correct
8 Correct 933 ms 85848 KB Output is correct
9 Correct 969 ms 86360 KB Output is correct
10 Correct 166 ms 85960 KB Output is correct
11 Correct 884 ms 85820 KB Output is correct
12 Correct 8 ms 76380 KB Output is correct
13 Correct 1117 ms 125592 KB Output is correct
14 Correct 2542 ms 129312 KB Output is correct
15 Correct 306 ms 123308 KB Output is correct
16 Correct 3428 ms 152880 KB Output is correct
17 Correct 3002 ms 129664 KB Output is correct
18 Correct 2263 ms 95452 KB Output is correct
19 Correct 253 ms 94496 KB Output is correct
20 Correct 2122 ms 98416 KB Output is correct
21 Correct 2299 ms 95864 KB Output is correct
22 Correct 1921 ms 129304 KB Output is correct
23 Correct 2025 ms 131476 KB Output is correct
24 Correct 5089 ms 134072 KB Output is correct
25 Correct 4606 ms 134852 KB Output is correct
26 Correct 4673 ms 131396 KB Output is correct
27 Correct 5040 ms 152596 KB Output is correct
28 Correct 382 ms 126488 KB Output is correct
29 Correct 4578 ms 130904 KB Output is correct
30 Correct 4540 ms 118324 KB Output is correct
31 Correct 4620 ms 118576 KB Output is correct
32 Correct 2086 ms 93640 KB Output is correct
33 Correct 224 ms 87752 KB Output is correct
34 Correct 813 ms 86864 KB Output is correct
35 Correct 848 ms 86868 KB Output is correct
36 Correct 2084 ms 87880 KB Output is correct
37 Correct 2071 ms 87632 KB Output is correct