oj.uz

답안 #398149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
398149 2021-05-03T20:04:02 Z bonopo 공장들 (JOI14_factories) C++14
100 / 100
 6094 ms 305228 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define el "\n"
#define f first
#define s second

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef long long ll;
const ll MM=5e5+5, MOD=1e9+7, LOG=20, INF=1e18;
int dep[MM], sz[MM], nxt[MM], in[MM], ot[MM], head[2*MM], ct=1, chn; ll dst[MM], spc[MM], pcl[LOG][MM];
pair<int,int> st[LOG][4*MM];
bool blk[MM], dn[LOG][MM];

struct E {int nxt; pair<int,int> v; } e[2*MM];
void add(int u, int v, int w){
    e[chn].v={v,w}; e[chn].nxt=head[u]; head[u]=chn++; }
int lg2(int x) {
    return 32-__builtin_clz(x)-1; }
void df1(int u, int pa) {
    dep[u]=dep[pa]+1; st[0][ct]=make_pair(dep[u], u); in[u]=ct++;
    for(int i=head[u]; i!=-1; i=e[i].nxt) {
        int v=e[i].v.f, w=e[i].v.s; if(v==pa) continue;
        dst[v]=dst[u]+w; df1(v, u); sz[u]+=sz[v];
        st[0][ct++]=make_pair(dep[u], u); }
    ot[u]=ct; }
inline int qry(int l, int r) {
    int lg=lg2(r-l+1);
    return min(st[lg][l], st[lg][r-(1<<lg)+1]).s; }
inline int lca(int u, int v) {
    if(in[u]>in[v]) return qry(in[v], in[u]);
    return qry(in[u], in[v]); }
void gsz(int u, int pa) {
    sz[u]=1;
    for(int i=head[u]; i!=-1; i=e[i].nxt) {
        int v=e[i].v.f; if(blk[v]||v==pa) continue;
        gsz(v, u); sz[u]+=sz[v]; } }
int ctr(int u, int pa, int nd) {
    for(int i=head[u]; i!=-1; i=e[i].nxt) {
        int v=e[i].v.f; if(blk[v]||v==pa) continue;
        if(sz[v]*2>nd) return ctr(v, u, nd); }
    return u; }
inline ll dist(int u, int c, int id) {
    if(pcl[id][u]) return pcl[id][u];
    return pcl[id][u]=dst[u]+dst[c]-2LL*dst[lca(u, c)]; }
void slv(int u, int pa) {
    gsz(u, -1); u=ctr(u, -1, sz[u]); blk[u]=1; nxt[u]=pa;
    for(int i=head[u]; i!=-1; i=e[i].nxt) {
        int v=e[i].v.f; if(!blk[v]) slv(v, u); } }
void Init(int N, int A[], int B[], int D[]) {
    memset(head, -1, sizeof(head));
    for(int i=0; i<N; ++i) spc[i]=INF;
    for(int i=0; i<N-1; ++i) {
        add(A[i], B[i], D[i]); add(B[i], A[i], D[i]); }
    df1(0, 0); slv(0, -1);
    for(int i=1; i<LOG; ++i)
        for(int j=1; j+(1<<i)-1<=ct; ++j)
            st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]); }
long long Query(int S, int X[], int T, int Y[]) {
    unordered_set<int> vs;
    for(int i=0, c, l=0; i<S; ++i, l=0) {
        c=X[i];
        while(c!=-1)
            spc[c]=min(spc[c], dist(X[i], c, l)), vs.insert(c), c=nxt[c], ++l; }
    long long ans=INF;
    for(int i=0, c, l=0; i<T; ++i, l=0) {
        c=Y[i];
        while(c!=-1)
            ans=min(ans, dist(Y[i], c, l)+spc[c]), c=nxt[c], ++l; }
    for(int x:vs) spc[x]=INF;
    return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 16484 KB Output is correct
2 Correct 596 ms 25948 KB Output is correct
3 Correct 779 ms 25992 KB Output is correct
4 Correct 574 ms 26192 KB Output is correct
5 Correct 717 ms 26480 KB Output is correct
6 Correct 387 ms 25408 KB Output is correct
7 Correct 773 ms 25868 KB Output is correct
8 Correct 799 ms 26100 KB Output is correct
9 Correct 715 ms 26412 KB Output is correct
10 Correct 385 ms 25420 KB Output is correct
11 Correct 768 ms 25884 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 16352 KB Output is correct
2 Correct 2908 ms 254156 KB Output is correct
3 Correct 3848 ms 272616 KB Output is correct
4 Correct 951 ms 203056 KB Output is correct
5 Correct 5063 ms 303588 KB Output is correct
6 Correct 4130 ms 274080 KB Output is correct
7 Correct 2628 ms 70544 KB Output is correct
8 Correct 605 ms 59000 KB Output is correct
9 Correct 3071 ms 75312 KB Output is correct
10 Correct 2682 ms 71640 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 16484 KB Output is correct
2 Correct 596 ms 25948 KB Output is correct
3 Correct 779 ms 25992 KB Output is correct
4 Correct 574 ms 26192 KB Output is correct
5 Correct 717 ms 26480 KB Output is correct
6 Correct 387 ms 25408 KB Output is correct
7 Correct 773 ms 25868 KB Output is correct
8 Correct 799 ms 26100 KB Output is correct
9 Correct 715 ms 26412 KB Output is correct
10 Correct 385 ms 25420 KB Output is correct
11 Correct 768 ms 25884 KB Output is correct
12 Correct 13 ms 16352 KB Output is correct
13 Correct 2908 ms 254156 KB Output is correct
14 Correct 3848 ms 272616 KB Output is correct
15 Correct 951 ms 203056 KB Output is correct
16 Correct 5063 ms 303588 KB Output is correct
17 Correct 4130 ms 274080 KB Output is correct
18 Correct 2628 ms 70544 KB Output is correct
19 Correct 605 ms 59000 KB Output is correct
20 Correct 3071 ms 75312 KB Output is correct
21 Correct 2682 ms 71640 KB Output is correct
22 Correct 3543 ms 258960 KB Output is correct
23 Correct 3902 ms 264056 KB Output is correct
24 Correct 4724 ms 279436 KB Output is correct
25 Correct 5117 ms 280784 KB Output is correct
26 Correct 5109 ms 274976 KB Output is correct
27 Correct 6094 ms 305228 KB Output is correct
28 Correct 1345 ms 207872 KB Output is correct
29 Correct 5304 ms 274448 KB Output is correct
30 Correct 5499 ms 273584 KB Output is correct
31 Correct 5583 ms 274400 KB Output is correct
32 Correct 2277 ms 77760 KB Output is correct
33 Correct 634 ms 59672 KB Output is correct
34 Correct 1540 ms 65972 KB Output is correct
35 Correct 1601 ms 66000 KB Output is correct
36 Correct 2107 ms 69080 KB Output is correct
37 Correct 2199 ms 69140 KB Output is correct