oj.uz

Submission #25318

# Submission time Handle Problem Language Result Execution time Memory
25318 2017-06-21T06:53:33 Z 서규호(#1060) Factories (JOI14_factories) C++14
15 / 100
 6000 ms 64056 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 color[500002];
bool check[500002];
vector<pair<int,lld>> edge[500002];

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]});
	}
}

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;
}

lld Query(int S, int X[], int T, int Y[]) {
	for(int i=1; i<=N; i++){
		color[i] = 0;
		check[i] = false;
	}
	for(int i=0; i<S; i++) color[X[i]+1] = 1;
	for(int i=0; i<T; i++) color[Y[i]+1] = 2;
	ans = Linf;
	dfs(1);
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 38448 KB Output is correct
2 Correct 1233 ms 38712 KB Output is correct
3 Correct 1453 ms 38712 KB Output is correct
4 Correct 1483 ms 38712 KB Output is correct
5 Correct 1526 ms 38800 KB Output is correct
6 Correct 539 ms 38736 KB Output is correct
7 Correct 1553 ms 38712 KB Output is correct
8 Correct 1519 ms 38712 KB Output is correct
9 Correct 1596 ms 38792 KB Output is correct
10 Correct 626 ms 38736 KB Output is correct
11 Correct 1599 ms 38712 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 38448 KB Output is correct
2 Execution timed out 6000 ms 64056 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

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