| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 482008 | 2021-10-22T15:16:43 Z | MilosMilutinovic | 공장들 (JOI14_factories) | C++14 | 5238 ms | 414512 KB |
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back
#define xx first
#define yy second
#define pii pair<int,int>
#define ll long long
using namespace std;
int n;
int sajz[500005];
int par[500005][23];
vector<pii> graf[500005];
bool was[500005];
vector<pair<int, ll>> cale[500005];
int dub[500005];
ll dep[500005];
void dfs(int u, int p){
dub[u] = dub[p] + 1;
par[u][0] = p;
ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
for(auto c:graf[u]){
if(c.xx != p){
dep[c.xx] = dep[u] + c.yy;
dfs(c.xx, u);
}
}
}
int lca(int u, int v){
if(dub[u] < dub[v])swap(u, v);
fb(i,22,0){
if(dub[par[u][i]] >= dub[v])u = par[u][i];
}
//cout << u << " " << v << "\n";
assert(dub[u] == dub[v]);
fb(i,22,0){
if(par[u][i] != par[v][i]){
u = par[u][i];
v = par[v][i];
}
}
if(u != v){
u = par[u][0];
v = par[v][0];
}
assert(u == v);
return u;
}
ll dist(int u, int v){
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void dfs1(int u, int p){
sajz[u] = 1;
for(auto c:graf[u]){
if(c.xx == p || was[c.xx]) {
continue;
}
dfs1(c.xx, u);
sajz[u] += sajz[c.xx];
}
}
int dfs2(int u, int p, int n){
for(auto c:graf[u]){
if(!was[c.xx] && c.xx != p && sajz[c.xx] * 2 >= n) {
return dfs2(c.xx, u, n);
}
}
return u;
}
int findcen(int u){
dfs1(u, u);
return dfs2(u, u, sajz[u]);
}
void solve(int u, int p, int st, ll s){
cale[u].pb({st,s});
for(auto c:graf[u]){
if(c.xx != p && !was[c.xx]){
solve(c.xx, u, st, s + c.yy);
}
}
}
void decomp(int u) {
u = findcen(u);
solve(u, u, u, 0);
was[u] = true;
for(auto c:graf[u]){
if(!was[c.xx])decomp(c.xx);
}
}
ll mn[500005];
void Init(int N, int* A, int* B, int* D){
n = N;
ff(i,0,n-2){
A[i]++;
B[i]++;
graf[A[i]].pb({B[i], D[i]});
graf[B[i]].pb({A[i], D[i]});
}
dfs(1, 0);
decomp(1);
// ff(i,1,n) assert((int) cale[i].size() <= 50);
ff(i,1,n)mn[i] = 1e18;
}
ll Query(int S, int* X, int T, int* Y){
ll ans = 1e18;
ff(i,0,S-1)X[i]++;
ff(i,0,T-1)Y[i]++;
//ff(i,0,S-1) ff(j,0,T-1) ans = min(ans, dist(X[i], Y[j]));
vector<int> cv;
ff(i,0,S-1){
assert(cale[i].size() <= 40);
for(auto c:cale[X[i]]){
mn[c.xx] = min(mn[c.xx], c.yy);
cv.pb(c.xx);
}
}
ff(i,0,T-1){
for(auto c:cale[Y[i]]){
ans = min(ans, mn[c.xx] + c.yy);
}
}
for(auto c:cv)mn[c] = 1e18;
return ans;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 24140 KB | Output is correct |
| 2 | Correct | 272 ms | 33488 KB | Output is correct |
| 3 | Correct | 289 ms | 33952 KB | Output is correct |
| 4 | Correct | 336 ms | 34336 KB | Output is correct |
| 5 | Correct | 310 ms | 34424 KB | Output is correct |
| 6 | Correct | 214 ms | 32876 KB | Output is correct |
| 7 | Correct | 306 ms | 33792 KB | Output is correct |
| 8 | Correct | 291 ms | 33984 KB | Output is correct |
| 9 | Correct | 310 ms | 34432 KB | Output is correct |
| 10 | Correct | 206 ms | 32836 KB | Output is correct |
| 11 | Correct | 287 ms | 33732 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 24076 KB | Output is correct |
| 2 | Correct | 2585 ms | 239636 KB | Output is correct |
| 3 | Correct | 4066 ms | 309952 KB | Output is correct |
| 4 | Correct | 1039 ms | 136744 KB | Output is correct |
| 5 | Correct | 4882 ms | 388160 KB | Output is correct |
| 6 | Correct | 3776 ms | 310272 KB | Output is correct |
| 7 | Correct | 1052 ms | 77672 KB | Output is correct |
| 8 | Correct | 432 ms | 69272 KB | Output is correct |
| 9 | Correct | 1284 ms | 105052 KB | Output is correct |
| 10 | Correct | 1113 ms | 92888 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 24140 KB | Output is correct |
| 2 | Correct | 272 ms | 33488 KB | Output is correct |
| 3 | Correct | 289 ms | 33952 KB | Output is correct |
| 4 | Correct | 336 ms | 34336 KB | Output is correct |
| 5 | Correct | 310 ms | 34424 KB | Output is correct |
| 6 | Correct | 214 ms | 32876 KB | Output is correct |
| 7 | Correct | 306 ms | 33792 KB | Output is correct |
| 8 | Correct | 291 ms | 33984 KB | Output is correct |
| 9 | Correct | 310 ms | 34432 KB | Output is correct |
| 10 | Correct | 206 ms | 32836 KB | Output is correct |
| 11 | Correct | 287 ms | 33732 KB | Output is correct |
| 12 | Correct | 13 ms | 24076 KB | Output is correct |
| 13 | Correct | 2585 ms | 239636 KB | Output is correct |
| 14 | Correct | 4066 ms | 309952 KB | Output is correct |
| 15 | Correct | 1039 ms | 136744 KB | Output is correct |
| 16 | Correct | 4882 ms | 388160 KB | Output is correct |
| 17 | Correct | 3776 ms | 310272 KB | Output is correct |
| 18 | Correct | 1052 ms | 77672 KB | Output is correct |
| 19 | Correct | 432 ms | 69272 KB | Output is correct |
| 20 | Correct | 1284 ms | 105052 KB | Output is correct |
| 21 | Correct | 1113 ms | 92888 KB | Output is correct |
| 22 | Correct | 3024 ms | 267068 KB | Output is correct |
| 23 | Correct | 3019 ms | 274228 KB | Output is correct |
| 24 | Correct | 4420 ms | 342316 KB | Output is correct |
| 25 | Correct | 4278 ms | 344540 KB | Output is correct |
| 26 | Correct | 4102 ms | 336212 KB | Output is correct |
| 27 | Correct | 5238 ms | 414512 KB | Output is correct |
| 28 | Correct | 1248 ms | 166248 KB | Output is correct |
| 29 | Correct | 3890 ms | 335172 KB | Output is correct |
| 30 | Correct | 3870 ms | 335192 KB | Output is correct |
| 31 | Correct | 3938 ms | 335428 KB | Output is correct |
| 32 | Correct | 1174 ms | 110264 KB | Output is correct |
| 33 | Correct | 442 ms | 70072 KB | Output is correct |
| 34 | Correct | 760 ms | 84144 KB | Output is correct |
| 35 | Correct | 784 ms | 84948 KB | Output is correct |
| 36 | Correct | 968 ms | 89924 KB | Output is correct |
| 37 | Correct | 995 ms | 90048 KB | Output is correct |