oj.uz

Submission #445570

# Submission time Handle Problem Language Result Execution time Memory
445570 2021-07-18T17:26:21 Z julian33 Factories (JOI14_factories) C++14
100 / 100
 4242 ms 213696 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=5e5+5,mxL=20; //make sure this is right
const int mod=1e9+7;

/*
build a virtual tree
for each node find the closest A and B
*/

vector<pii> graph[mxN];
vector<int> vt[mxN];

ll up[mxN][2],down[mxN][2],yes[mxN][2],bl[mxN][mxL],st[mxN],en[mxN],ht[mxN],dep[mxN],cur;
ll ans=1e18;

void dfs(int at,int p){
    bl[at][0]=~p?p:at;
    for(int i=1;i<mxL;i++)
        bl[at][i]=bl[bl[at][i-1]][i-1];
    st[at]=++cur;
    for(auto &[i,w]:graph[at]){
        if(i==p)
            continue;
        ht[i]=ht[at]+1;
        dep[i]=dep[at]+w;
        dfs(i,at);
    }
    en[at]=++cur;
}

int jump(int a,int k){
    for(int i=0;i<mxL;i++){
        if(k&(1<<i))
            a=bl[a][i];
    }
    return a;
}

int lca(int a,int b){
    if(ht[a]>ht[b])
        swap(a,b);
    int diff=ht[b]-ht[a];
    b=jump(b,diff);
    if(a==b)
        return a;
    for(int i=mxL-1;i>=0;i--){
        if(bl[a][i]!=bl[b][i]){
            a=bl[a][i];
            b=bl[b][i];
        }
    }
    return bl[a][0];
}

ll dist(int a,int b){
    return dep[b]-dep[a];
}

bool anc(int a,int b){
    return st[a]<=st[b] && en[a]>=en[b];
}

void dfs1(int at,int p){
    for(int &i:vt[at]){
        if(i==p)
            continue;
        dfs1(i,at);
        mina(down[at][0],down[i][0]+dist(at,i));
        mina(down[at][1],down[i][1]+dist(at,i));
    }
    if(yes[at][0])
        down[at][0]=0;
    if(yes[at][1])
        down[at][1]=0;
}

void dfs2(int at,int p){
    for(int &i:vt[at]){
        if(i==p)
            continue;
        up[i][0]=min(up[at][0],down[at][0])+dist(at,i);
        up[i][1]=min(up[at][1],down[at][1])+dist(at,i);
        dfs2(i,at);
    }
    mina(ans,min(up[at][0],down[at][0])+min(up[at][1],down[at][1]));
}

void solve(int root){
    ans=1e18;
    dfs1(root,-1);
    dfs2(root,-1);
}

void build(vector<int> a){
    sort(a.begin(),a.end(),[&](int x,int y){return st[x]<st[y];});
    int len=sz(a);
    for(int i=0;i<len-1;i++){
        a.pb(lca(a[i],a[i+1]));
    }
    sort(a.begin(),a.end(),[&](int x,int y){return st[x]<st[y];});
    a.resize(unique(a.begin(),a.end())-a.begin());
    for(auto &i:a){
        up[i][0]=up[i][1]=1e16;
        down[i][0]=down[i][1]=1e16;
        vt[i].clear();
    }
    stack<int> stk; stk.push(a[0]);
    for(int i=1;i<sz(a);i++){
        while(sz(stk)>=2 && !anc(stk.top(),a[i])){
            int k=stk.top(); stk.pop();
            vt[stk.top()].pb(k);
        }
        stk.push(a[i]);
    }
    while(sz(stk)>=2){
        int k=stk.top();
        stk.pop();
        vt[stk.top()].pb(k);
    }
    solve(stk.top());
}

void Init(int N, int A[], int B[], int D[]){
    for(int i=0;i<N-1;i++){
        graph[A[i]].pb({B[i],D[i]});
        graph[B[i]].pb({A[i],D[i]});
    }
    dfs(0,-1);
}

long long Query(int S, int X[], int T, int Y[]){
    vector<int> a;
    for(int i=0;i<S;i++){
        yes[X[i]][0]=1;
        a.pb(X[i]);
    }
    for(int i=0;i<T;i++){
        yes[Y[i]][1]=1;
        a.pb(Y[i]);
    }
    build(a);
    for(int i=0;i<S;i++){
        yes[X[i]][0]=0;
    }
    for(int i=0;i<T;i++){
        yes[Y[i]][1]=0;
    }
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:49:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto &[i,w]:graph[at]){
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24396 KB Output is correct
2 Correct 1108 ms 42892 KB Output is correct
3 Correct 1122 ms 42920 KB Output is correct
4 Correct 1089 ms 43080 KB Output is correct
5 Correct 923 ms 43104 KB Output is correct
6 Correct 742 ms 42728 KB Output is correct
7 Correct 1108 ms 42916 KB Output is correct
8 Correct 1101 ms 43096 KB Output is correct
9 Correct 921 ms 43108 KB Output is correct
10 Correct 739 ms 42824 KB Output is correct
11 Correct 1130 ms 43136 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24012 KB Output is correct
2 Correct 1923 ms 174952 KB Output is correct
3 Correct 2482 ms 179844 KB Output is correct
4 Correct 1392 ms 176004 KB Output is correct
5 Correct 2602 ms 211652 KB Output is correct
6 Correct 2802 ms 179204 KB Output is correct
7 Correct 2633 ms 76220 KB Output is correct
8 Correct 1395 ms 76744 KB Output is correct
9 Correct 2421 ms 82628 KB Output is correct
10 Correct 2624 ms 77692 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24396 KB Output is correct
2 Correct 1108 ms 42892 KB Output is correct
3 Correct 1122 ms 42920 KB Output is correct
4 Correct 1089 ms 43080 KB Output is correct
5 Correct 923 ms 43104 KB Output is correct
6 Correct 742 ms 42728 KB Output is correct
7 Correct 1108 ms 42916 KB Output is correct
8 Correct 1101 ms 43096 KB Output is correct
9 Correct 921 ms 43108 KB Output is correct
10 Correct 739 ms 42824 KB Output is correct
11 Correct 1130 ms 43136 KB Output is correct
12 Correct 18 ms 24012 KB Output is correct
13 Correct 1923 ms 174952 KB Output is correct
14 Correct 2482 ms 179844 KB Output is correct
15 Correct 1392 ms 176004 KB Output is correct
16 Correct 2602 ms 211652 KB Output is correct
17 Correct 2802 ms 179204 KB Output is correct
18 Correct 2633 ms 76220 KB Output is correct
19 Correct 1395 ms 76744 KB Output is correct
20 Correct 2421 ms 82628 KB Output is correct
21 Correct 2624 ms 77692 KB Output is correct
22 Correct 3755 ms 182932 KB Output is correct
23 Correct 3336 ms 184176 KB Output is correct
24 Correct 4146 ms 187804 KB Output is correct
25 Correct 4209 ms 190116 KB Output is correct
26 Correct 4073 ms 182124 KB Output is correct
27 Correct 4242 ms 213696 KB Output is correct
28 Correct 2297 ms 182148 KB Output is correct
29 Correct 4096 ms 180824 KB Output is correct
30 Correct 4185 ms 180208 KB Output is correct
31 Correct 4173 ms 180744 KB Output is correct
32 Correct 2390 ms 84972 KB Output is correct
33 Correct 1462 ms 79356 KB Output is correct
34 Correct 2277 ms 74812 KB Output is correct
35 Correct 2297 ms 74820 KB Output is correct
36 Correct 2566 ms 75720 KB Output is correct
37 Correct 2554 ms 75660 KB Output is correct