oj.uz

Submission #398151

# Submission time Handle Problem Language Result Execution time Memory
398151 2021-05-03T20:10:09 Z bonopo Factories (JOI14_factories) C++14
100 / 100
 4398 ms 303576 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];

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[]) {
    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)), 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 i=0, c; i<S; ++i) {
        c=X[i];
        while(c!=-1)
            spc[c]=INF, c=nxt[c]; }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16460 KB Output is correct
2 Correct 374 ms 25900 KB Output is correct
3 Correct 437 ms 25924 KB Output is correct
4 Correct 398 ms 25924 KB Output is correct
5 Correct 417 ms 26180 KB Output is correct
6 Correct 338 ms 25412 KB Output is correct
7 Correct 426 ms 25888 KB Output is correct
8 Correct 411 ms 25960 KB Output is correct
9 Correct 419 ms 26212 KB Output is correct
10 Correct 290 ms 25412 KB Output is correct
11 Correct 399 ms 25924 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16332 KB Output is correct
2 Correct 2045 ms 254360 KB Output is correct
3 Correct 2696 ms 272580 KB Output is correct
4 Correct 767 ms 202936 KB Output is correct
5 Correct 3530 ms 303576 KB Output is correct
6 Correct 2809 ms 273856 KB Output is correct
7 Correct 1167 ms 70396 KB Output is correct
8 Correct 460 ms 58900 KB Output is correct
9 Correct 1330 ms 75160 KB Output is correct
10 Correct 1218 ms 71804 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16460 KB Output is correct
2 Correct 374 ms 25900 KB Output is correct
3 Correct 437 ms 25924 KB Output is correct
4 Correct 398 ms 25924 KB Output is correct
5 Correct 417 ms 26180 KB Output is correct
6 Correct 338 ms 25412 KB Output is correct
7 Correct 426 ms 25888 KB Output is correct
8 Correct 411 ms 25960 KB Output is correct
9 Correct 419 ms 26212 KB Output is correct
10 Correct 290 ms 25412 KB Output is correct
11 Correct 399 ms 25924 KB Output is correct
12 Correct 10 ms 16332 KB Output is correct
13 Correct 2045 ms 254360 KB Output is correct
14 Correct 2696 ms 272580 KB Output is correct
15 Correct 767 ms 202936 KB Output is correct
16 Correct 3530 ms 303576 KB Output is correct
17 Correct 2809 ms 273856 KB Output is correct
18 Correct 1167 ms 70396 KB Output is correct
19 Correct 460 ms 58900 KB Output is correct
20 Correct 1330 ms 75160 KB Output is correct
21 Correct 1218 ms 71804 KB Output is correct
22 Correct 2665 ms 254648 KB Output is correct
23 Correct 2696 ms 259080 KB Output is correct
24 Correct 3699 ms 274456 KB Output is correct
25 Correct 3612 ms 277880 KB Output is correct
26 Correct 3653 ms 274604 KB Output is correct
27 Correct 4398 ms 300336 KB Output is correct
28 Correct 1036 ms 206948 KB Output is correct
29 Correct 3652 ms 274100 KB Output is correct
30 Correct 3623 ms 273444 KB Output is correct
31 Correct 3566 ms 274152 KB Output is correct
32 Correct 1294 ms 76236 KB Output is correct
33 Correct 477 ms 59368 KB Output is correct
34 Correct 913 ms 65616 KB Output is correct
35 Correct 1002 ms 65608 KB Output is correct
36 Correct 1188 ms 68940 KB Output is correct
37 Correct 1175 ms 69128 KB Output is correct