# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
25311 |
2017-06-21T06:33:40 Z |
김현수(#1059) |
Factories (JOI14_factories) |
C++11 |
|
6000 ms |
209876 KB |
#include<bits/stdc++.h>
#include "factories.h"
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e18, N = 500005, L = 20;
ll n, s[N], e[N], inv[N], dep[N], frd[N];
ll par[L][N], dt[3][N], typ[N], cc, ans;
vector<pll> adj[N], tmp[N];
void calc (ll C, ll P) {
s[C] = ++cc;
inv[cc] = C;
for(auto &T : adj[C]) {
ll A, B; tie(A, B) = T;
if(A == P) continue;
par[0][A] = C;
frd[A] = frd[C] + B;
dep[A] = dep[C] + 1;
calc(A, C);
}
e[C] = cc;
}
ll getlca (ll A, ll B) {
if(dep[A] < dep[B]) swap(A, B);
for(ll i=L;i--;) {
if(dep[A] - dep[B] >= (1<<i)) {
A = par[i][A];
}
}
if(A == B) return A;
for(ll i=L;i--;) {
if(par[i][A] != par[i][B]) {
A = par[i][A]; B = par[i][B];
}
}
return par[0][A];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(ll i=0;i<n-1;i++) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
calc(0, 0);
for(ll k=1;k<L;k++) {
for(ll i=0;i<n;i++) {
par[k][i] = par[k-1][par[k-1][i]];
}
}
}
void dfs (ll C, ll P) {
dt[1][C] = dt[2][C] = inf;
dt[typ[C]][C] = 0;
for(auto &T : tmp[C]) {
ll A, B; tie(A, B) = T;
if(A == P) continue;
dfs(A, C);
dt[1][C] = min(dt[1][C], dt[1][A] + B);
dt[2][C] = min(dt[2][C], dt[2][A] + B);
}
ans = min(ans, dt[1][C]+dt[2][C]);
}
ll Query(int C1, int X[], int C2, int Y[]) {
vector<ll> V, S;
for(ll i=0;i<C1;i++) {
V.push_back(s[X[i]]);
typ[X[i]] = 1;
}
for(ll i=0;i<C2;i++) {
V.push_back(s[Y[i]]);
typ[Y[i]] = 2;
}
sort(V.begin(), V.end());
for(ll i=1;i<C1+C2;i++) {
ll A = inv[V[i-1]], B = inv[V[i]];
V.push_back(s[getlca(A, B)]);
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
for(auto &T : V) tmp[inv[T]].clear();
for(auto &T : V) {
ll A = inv[T];
while(!S.empty()) {
ll P = S.back();
if(s[P] <= s[A] && e[A] <= e[P]) break;
else S.pop_back();
}
if(!S.empty()) {
ll P = S.back(), D = frd[A] - frd[P];
tmp[A].push_back({P, D});
tmp[P].push_back({A, D});
}
S.push_back(A);
}
ans = inf;
dfs(inv[V[0]], inv[V[0]]);
for(auto &T : V) typ[inv[T]] = 0;
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
161144 KB |
Output is correct |
2 |
Correct |
1813 ms |
161740 KB |
Output is correct |
3 |
Correct |
1946 ms |
161544 KB |
Output is correct |
4 |
Correct |
1673 ms |
161856 KB |
Output is correct |
5 |
Correct |
1039 ms |
161776 KB |
Output is correct |
6 |
Correct |
1646 ms |
161604 KB |
Output is correct |
7 |
Correct |
1939 ms |
161544 KB |
Output is correct |
8 |
Correct |
1766 ms |
161852 KB |
Output is correct |
9 |
Correct |
936 ms |
161772 KB |
Output is correct |
10 |
Correct |
1489 ms |
161604 KB |
Output is correct |
11 |
Correct |
1953 ms |
161544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
161012 KB |
Output is correct |
2 |
Execution timed out |
6000 ms |
201388 KB |
Execution timed out |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6000 ms |
209876 KB |
Execution timed out |
2 |
Halted |
0 ms |
0 KB |
- |