oj.uz

Submission #25363

# Submission time Handle Problem Language Result Execution time Memory
25363 2017-06-21T10:55:08 Z suhgyuho_william Factories (JOI14_factories) C++14
15 / 100
 6000 ms 225788 KB 
#include "factories.h"
#include <bits/stdc++.h>

#define pb push_back
#define lld long long
#define Linf 1000000000000000000LL

using namespace std;

int N; lld ans;
int lev[500002];
pair<int,lld> par[500002][20];
int color[500002];
bool check[500002];
vector<pair<int,lld>> edge[500002];

void makepar(int x){
	check[x] = true;
	for(auto &i : edge[x]){
		if(check[i.first]) continue;
		lev[i.first] = lev[x]+1;
		par[i.first][0].first = x; par[i.first][0].second = i.second;
		for(int j=1; j<=19; j++){
			par[i.first][j].first = par[par[i.first][j-1].first][j-1].first;
			par[i.first][j].second = par[par[i.first][j-1].first][j-1].second+par[i.first][j-1].second;
		}
		makepar(i.first);
	}
}

void Init(int n, int A[], int B[], int D[]) {
	N = n;
	for(int i=0; i<N-1; i++){
		A[i]++; B[i]++;
		edge[A[i]].pb({B[i],D[i]});
		edge[B[i]].pb({A[i],D[i]});
	}
	makepar(1);
}

pair<lld,lld> dfs(int x){
	check[x] = true;
	pair<lld,lld> tmp = {Linf,Linf};
	if(color[x] == 1) tmp.first = 0;
	else if(color[x] == 2) tmp.second = 0;
	for(auto &i : edge[x]){
		if(check[i.first]) continue;
		pair<lld,lld> t = dfs(i.first);
		t.first += i.second; t.second += i.second;
		ans = min(ans,tmp.first+t.second);
		ans = min(ans,tmp.second+t.first);
		tmp.first = min(tmp.first,t.first);
		tmp.second= min(tmp.second,t.second);
	}
	return tmp;
}

int getpar(int x,int y){
	if(lev[x] > lev[y]) swap(x,y);
	for(int i=0; i<=19; i++){
		if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
		y = par[y][i].first;
	}
	if(x == y) return x;
	int t;
	for(int i=0; i<=19; i++){
		if(par[x][i].first == par[y][i].first){
			t = i;
			break;
		}
	}
	while(t != 0){
		t--;
		if(par[x][t].first != par[y][t].first){
			x = par[x][t].first;
			y = par[y][t].first;
		}
	}
	if(par[x][0].first == 0 && x == 1) exit(-1);
	return par[x][0].first;
}
lld getdis(int x,int y){
	if(lev[x] > lev[y]) swap(x,y);
	lld tsum = 0;
	for(int i=0; i<=19; i++){
		if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
		tsum += par[y][i].second;
		y = par[y][i].first;
	}
	return tsum;
}

lld Query(int S, int X[], int T, int Y[]) {
	for(int i=0; i<S; i++) X[i]++;
	for(int i=0; i<T; i++) Y[i]++;
	if(S <= 10 && T <= 10){
		ans = Linf;
		for(int i=0; i<S; i++){
			for(int j=0; j<T; j++){
				int tmp = getpar(X[i],Y[j]);
				ans = min(ans,getdis(X[i],tmp)+getdis(Y[j],tmp));
			}
		}
		return ans;
	}
	for(int i=1; i<=N; i++){
		color[i] = 0;
		check[i] = false;
	}
	for(int i=0; i<S; i++) color[X[i]] = 1;
	for(int i=0; i<T; i++) color[Y[i]] = 2;
	ans = Linf;
	dfs(1);
	return ans;
}

Compilation message

factories.cpp: In function 'int getpar(int, int)':
factories.cpp:73:6: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
   t--;
      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 196652 KB Output is correct
2 Correct 523 ms 196916 KB Output is correct
3 Correct 1453 ms 196916 KB Output is correct
4 Correct 1183 ms 196916 KB Output is correct
5 Correct 729 ms 197004 KB Output is correct
6 Correct 346 ms 196940 KB Output is correct
7 Correct 1413 ms 196916 KB Output is correct
8 Correct 1369 ms 196916 KB Output is correct
9 Correct 603 ms 197004 KB Output is correct
10 Correct 459 ms 196940 KB Output is correct
11 Correct 1493 ms 196916 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 196652 KB Output is correct
2 Correct 2743 ms 222260 KB Output is correct
3 Execution timed out 6000 ms 225788 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 222260 KB Execution timed out
2 Halted 0 ms 0 KB -