oj.uz

Submission #52294

# Submission time Handle Problem Language Result Execution time Memory
52294 2018-06-25T08:12:02 Z 노영훈(#1346) Factories (JOI14_factories) C++11
0 / 100
 8000 ms 226548 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;

const int MX=500010, LG=22;
const ll inf=2e17;

struct edge {
    int to; ll co;
} st[MX][LG];

int n, dep[MX];
vector<edge> G[MX];

ll dist(int u, int v){
    if(dep[u]<dep[v]) swap(u,v);
    // u is deeper
    ll ans=0;
    for(int i=LG-1; i>=0; i--){
        if(dep[st[u][i].to]>=dep[v])
            ans+=st[u][i].co, u=st[u][i].to;
    }
    if(u==v) return ans;
    for(int i=LG-1; i>=0; i--){
        if(st[u][i].to != st[v][i].to){
            ans+=st[u][i].co + st[v][i].co;
            u=st[u][i].to; v=st[v][i].to;
        }
    }
    ans+=st[u][0].co+st[v][0].co;
    return ans;
}

void dfs1(int v, int p){
    for(int i=1; i<LG; i++){
        int anc=st[v][i-1].to;
        st[v][i].to=st[anc][i-1].to;
        st[v][i].co=st[anc][i-1].co + st[v][i-1].co;
    }
    for(edge &e:G[v]){
        int x=e.to; ll c=e.co;
        if(x==p) continue;
        dep[x]=dep[v]+1;
        st[x][0]={v,c};
        dfs1(x,v);
    }
}

void Init(int N, int A[], int B[], int D[]){
    n=N;
    for(int i=0; i<=n-2; i++){
        int u=A[i]+1, v=B[i]+1;
        G[u].push_back({v,D[i]});
        G[v].push_back({u,D[i]});
    }
    dep[1]=0, dfs1(1,0);
}

ll Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<S; i++) X[i]++;
    for(int i=0; i<T; i++) Y[i]++;


    ll ans=inf;
    for(int i=0; i<S; i++)
        for(int j=0; j<T; j++){
            ans=min(ans, dist(X[i], Y[j]));
            // cout<<X[i]<<' '<<Y[i]<<": "<<dist(X[i], Y[i])<<'\n';
        }

    return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 12536 KB Output is correct
2 Execution timed out 8077 ms 22140 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 22140 KB Output is correct
2 Correct 3291 ms 225016 KB Output is correct
3 Execution timed out 8066 ms 226548 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 12536 KB Output is correct
2 Execution timed out 8077 ms 22140 KB Time limit exceeded
3 Halted 0 ms 0 KB -