# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
25279 |
2017-06-21T05:48:51 Z |
김동현(#1058) |
공장들 (JOI14_factories) |
C++14 |
|
6000 ms |
114884 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; }
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){
md[i.x] = nd;
pq.push({i.x, nd});
}
}
}
ll ret = inf;
for(int i = 0; i < y; i++) ret = min(ret, md[b[i] + 1]);
return ret;
}
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 > 2LL * n) return f(S, X, T, Y);
else return g(S, X, T, Y);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
84836 KB |
Output is correct |
2 |
Correct |
1012 ms |
85232 KB |
Output is correct |
3 |
Correct |
3003 ms |
85100 KB |
Output is correct |
4 |
Correct |
1179 ms |
85380 KB |
Output is correct |
5 |
Correct |
1026 ms |
85388 KB |
Output is correct |
6 |
Correct |
1073 ms |
85400 KB |
Output is correct |
7 |
Correct |
2933 ms |
85100 KB |
Output is correct |
8 |
Correct |
1126 ms |
85100 KB |
Output is correct |
9 |
Correct |
1173 ms |
85388 KB |
Output is correct |
10 |
Correct |
993 ms |
85400 KB |
Output is correct |
11 |
Correct |
2969 ms |
85100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
84836 KB |
Output is correct |
2 |
Correct |
5523 ms |
110444 KB |
Output is correct |
3 |
Execution timed out |
6000 ms |
114884 KB |
Execution timed out |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
6000 ms |
113644 KB |
Execution timed out |
2 |
Halted |
0 ms |
0 KB |
- |