# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
25318 |
2017-06-21T06:53:33 Z |
서규호(#1060) |
Factories (JOI14_factories) |
C++14 |
|
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;
}
# |
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 |
# |
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 |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6000 ms |
64056 KB |
Execution timed out |
2 |
Halted |
0 ms |
0 KB |
- |