oj.uz

Submission #1048367

# Submission time Handle Problem Language Result Execution time Memory
1048367 2024-08-08T07:06:09 Z tamir1 Factories (JOI14_factories) C++17
0 / 100
 8000 ms 135012 KB 
#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ff first
#define ss second
using namespace std;
ll dis[100001];
int jump[21][100001],dep[100001];
vector<pair<int,ll>> v[100001]; 
void dfs(int x,int y){
	int nx,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=1e18;
	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:13: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]
   13 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 27320 KB Output is correct
2 Execution timed out 8074 ms 38992 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 27228 KB Output is correct
2 Runtime error 281 ms 135012 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 27320 KB Output is correct
2 Execution timed out 8074 ms 38992 KB Time limit exceeded
3 Halted 0 ms 0 KB -