oj.uz

Submission #1048448

# Submission time Handle Problem Language Result Execution time Memory
1048448 2024-08-08T07:40:48 Z tamir1 Factories (JOI14_factories) C++17
18 / 100
 8000 ms 152568 KB 
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
ll dis[500001];
int jump[21][500001],dep[500001];
vector<pair<int,ll>> v[500001]; 
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];
}

void Init(int N, int A[], int B[], int D[]) {
	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]];
		}
	}
}
long long Query(int S, int X[], int T, int Y[]) {
	ll res=LLONG_MAX;
	for(int i=0;i<S;i++){
		for(int j=0;j<T;j++){	
			res=min(res,dis[X[i]]+dis[Y[j]]-2*dis[lca(X[i],Y[j])]);
		}
	}
	return res;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:14: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]
   14 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 72536 KB Output is correct
2 Execution timed out 8010 ms 81716 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 72284 KB Output is correct
2 Correct 741 ms 117740 KB Output is correct
3 Correct 1534 ms 128336 KB Output is correct
4 Correct 500 ms 122084 KB Output is correct
5 Correct 1077 ms 152568 KB Output is correct
6 Correct 1195 ms 129104 KB Output is correct
7 Correct 2220 ms 96364 KB Output is correct
8 Correct 467 ms 95420 KB Output is correct
9 Correct 1562 ms 99260 KB Output is correct
10 Correct 1419 ms 96760 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 72536 KB Output is correct
2 Execution timed out 8010 ms 81716 KB Time limit exceeded
3 Halted 0 ms 0 KB -