# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
25271 |
2017-06-21T05:39:52 Z |
김동현(#1058) |
Factories (JOI14_factories) |
C++14 |
|
6000 ms |
135148 KB |
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct E{
int x; ll d;
bool operator<(const E &oth) const {
return d > oth.d;
}
};
const ll inf = 1e18;
int n, c[500010], d[500010], sp[19][500010];
ll dd[500010], md[500010];
vector<E> e[500010];
priority_queue<E> pq;
void dfs(int x, int p, int de, ll dde){
sp[0][x] = p;
d[x] = de;
dd[x] = dde;
for(int i = 1; i < 19; i++) sp[i][x] = sp[i - 1][sp[i - 1][x]];
for(auto &i : e[x]){
if(i.x != p) dfs(i.x, x, de + 1, dde + i.d);
}
}
int lca(int x, int y){
if(d[x] < d[y]) swap(x, y);
for(int i = 18; i >= 0; i--){
if(d[sp[i][x]] >= d[y]) x = sp[i][x];
}
if(x == y) return x;
for(int i = 18; i >= 0; i--){
if(sp[i][x] && sp[i][y] && sp[i][x] != sp[i][y]){
x = sp[i][x];
y = sp[i][y];
}
}
return sp[0][x];
}
ll dis(int x, int y){
return dd[x] + dd[y] - 2 * dd[lca(x, y)];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0, x, y, z; i < n - 1; i++){
x = A[i] + 1; y = B[i] + 1; z = D[i];
e[x].push_back({y, z});
e[y].push_back({x, z});
}
dfs(1, 0, 1, 0);
}
ll f(int x, int a[], int y, int b[]){
fill(md + 1, md + n + 1, inf);
fill(c + 1, c + n + 1, 0);
for(int i = 0; i < x; i++){ pq.push({a[i] + 1, 0}); md[a[i] + 1] = 0; }
for(int i = 0; i < y; i++){
c[b[i] + 1] = 1;
if(!md[b[i] + 1]) return 0;
}
while(!pq.empty()){
E cur = pq.top(); pq.pop();
for(auto &i : e[cur.x]){
ll nd = cur.d + i.d;
if(md[i.x] > nd){
if(c[i.x]) return nd;
md[i.x] = nd;
pq.push({i.x, nd});
}
}
}
}
ll g(int x, int a[], int y, int b[]){
ll ret = inf;
for(int i = 0; i < x; i++){
for(int j = 0; j < y; j++){
ret = min(ret, dis(a[i] + 1, b[j] + 1));
}
}
return ret;
}
ll Query(int S, int X[], int T, int Y[]) {
if(1LL * S * T > n) return f(S, X, T, Y);
else return g(S, X, T, Y);
}
Compilation message
factories.cpp: In function 'll f(int, int*, int, int*)':
factories.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
85716 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
84836 KB |
Output is correct |
2 |
Correct |
5283 ms |
110444 KB |
Output is correct |
3 |
Execution timed out |
6000 ms |
114888 KB |
Execution timed out |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1546 ms |
135148 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |