# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
33040 |
2017-10-19T04:22:06 Z |
aome |
Factories (JOI14_factories) |
C++14 |
|
6000 ms |
127352 KB |
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int N = 500005;
const long long INF = 1e18;
typedef pair<int, int> ii;
int n, h[N];
int cnt, st[N];
int par[20][N];
long long res;
long long dis[N];
long long f[2][N];
bool flag[2][N];
vector<ii> G[N];
void dfs(int u) {
st[u] = cnt++;
for (auto v : G[u]) {
if (par[0][u] == v.first) continue;
par[0][v.first] = u, dis[v.first] = dis[u] + v.second;
h[v.first] = h[u] + 1, dfs(v.first);
}
}
int lca(int u, int v) {
if (h[u] > h[v]) swap(u, v);
for (int i = 18; i >= 0; --i) {
if (h[par[i][v]] >= h[u]) v = par[i][v];
}
for (int i = 18; i >= 0; --i) {
if (par[i][v] != par[i][u]) {
v = par[i][v], u = par[i][u];
}
}
return (u == v) ? u : par[0][u];
}
void Init(int n, int a[], int b[], int d[]) {
for (int i = 0; i < (n - 1); ++i) {
G[a[i]].push_back(ii(b[i], d[i]));
G[b[i]].push_back(ii(a[i], d[i]));
}
dfs(0);
for (int i = 1; i <= 18; ++i) {
for (int j = 1; j <= n; ++j) {
par[i][j] = par[i - 1][par[i - 1][j]];
}
}
}
vector<int> nG[N];
void solve(int u) {
for (int i = 0; i < 2; ++i) {
if (flag[i][u]) f[i][u] = min(f[i][u], dis[u]);
}
for (auto v : nG[u]) {
solve(v);
for (int i = 0; i < 2; ++i) f[i][u] = min(f[i][u], f[i][v]);
}
long long mn[2];
mn[0] = mn[1] = INF;
for (auto v : nG[u]) {
for (int i = 0; i < 2; ++i) {
res = min(res, f[i][v] + mn[i ^ 1] - 2 * dis[u]);
}
for (int i = 0; i < 2; ++i) {
mn[i] = min(mn[i], f[i][v]);
}
}
for (int i = 0; i < 2; ++i) {
if (flag[i ^ 1][u]) res = min(res, mn[i] - dis[u]);
}
}
long long Query(int s, int x[], int t, int y[]) {
vector<int> ver;
for (int i = 0; i < s; ++i) ver.push_back(x[i]), flag[0][x[i]] = 1;
for (int i = 0; i < t; ++i) ver.push_back(y[i]), flag[1][y[i]] = 1;
sort(ver.begin(), ver.end(), [&](int x, int y) {
return st[x] < st[y];
});
int sz = ver.size();
for (int i = 1; i < sz; ++i) {
ver.push_back(lca(ver[i - 1], ver[i]));
}
sort(ver.begin(), ver.end(), [&](int x, int y) {
return st[x] < st[y];
});
ver.erase(unique(ver.begin(), ver.end()), ver.end());
sz = ver.size();
for (int i = 1; i < sz; ++i) {
int p = lca(ver[i - 1], ver[i]);
nG[p].push_back(ver[i]);
// cout << p << ' ' << ver[i] << '\n';
}
for (int i = 0; i < sz; ++i) {
f[0][ver[i]] = f[1][ver[i]] = INF;
}
res = INF, solve(ver[0]);
for (int i = 0; i < sz; ++i) {
flag[0][ver[i]] = flag[1][ver[i]] = 0;
nG[ver[i]].clear();
}
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
103392 KB |
Output is correct |
2 |
Correct |
3186 ms |
103800 KB |
Output is correct |
3 |
Correct |
3483 ms |
103656 KB |
Output is correct |
4 |
Correct |
3219 ms |
103816 KB |
Output is correct |
5 |
Correct |
2916 ms |
103872 KB |
Output is correct |
6 |
Correct |
2296 ms |
103692 KB |
Output is correct |
7 |
Correct |
3606 ms |
103656 KB |
Output is correct |
8 |
Correct |
3286 ms |
103788 KB |
Output is correct |
9 |
Correct |
2676 ms |
103880 KB |
Output is correct |
10 |
Correct |
2299 ms |
103692 KB |
Output is correct |
11 |
Correct |
3503 ms |
103656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
103392 KB |
Output is correct |
2 |
Execution timed out |
6000 ms |
122136 KB |
Execution timed out |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
6000 ms |
127352 KB |
Execution timed out |
2 |
Halted |
0 ms |
0 KB |
- |