oj.uz

Submission #645441

# Submission time Handle Problem Language Result Execution time Memory
645441 2022-09-27T06:47:31 Z karrigan Factories (JOI14_factories) C++14
18 / 100
 8000 ms 193600 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
struct edg{
int v;
long long w;
};
vector<edg>g[500009];
long long dis[500009];
long long dep[500009];
long long st[500009][21];
long long sub[500009];
int use[500009];
void dfs(int u,int par){
    for (auto v:g[u]){
        if (v.v==par)continue;
        dis[v.v]=dis[u]+v.w;
        dep[v.v]=dep[u]+1;
        st[v.v][0]=u;
        dfs(v.v,u);
    }
}
int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for (int i=20;i>=0;i--){
    if (k>>i&1){
        u=st[u][i];
    }
}
if (u==v)return u;
for (int i=20;i>=0;i--){
    if (st[u][i]==-1||st[v][i]==-1)continue;
    if (st[u][i]!=st[v][i]){
        u=st[u][i];
        v=st[v][i];
    }
}
return st[u][0];
}
long long cal(int u,int v){
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
/*int dfs2(int u,int par){
    sub[u]=1;
    for (auto v:g[u]){
        int lm=v.v;
        if (use[lm]||lm==par)continue;
        dfs2(lm,u);
        sub[u]+=sub[lm];
    }
    return sub[u];
}
int centroid(int u,int p,int sz){
    for (auto v:g[u]){
        if (use[v.v]||v.v==p)continue;
        if (sub[v.v]*2>sz)return centroid(v.v,u,sz);
    }
    return u;
}
int par[500009];
long long mxx[500009];
int decompose(int u,int p){
int sz=dfs2(u,0);
int cen=centroid(u,0,sz);
use[cen]=1;
if (p!=0){
    par[cen]=p;
}
for (auto v:g[cen]){
    if (use[v.v])continue;
    decompose(v.v,cen);
}
return cen;
}*/
void Init(int N,int A[],int B[],int D[]){
for (int i=0;i<N-1;i++){
    g[A[i]].push_back({B[i],D[i]});
    g[B[i]].push_back({A[i],D[i]});
}
dfs(0,-1);
st[0][0]=-1;
for (int i=1;i<=20;i++){
    for (int j=0;j<N;j++){
        st[j][i]=st[st[j][i-1]][i-1];
    }
}
/*for (int i=1;i<=N;i++){
    mxx[i]=1e17;
}
decompose(1,0);*/
}
/*void update(int u,int pos){
if (pos==0)return;
mxx[pos]=min(mxx[pos],cal(u,pos));
update(u,par[pos]);
}
void res(int u,int pos){
if (pos==0)return;
mxx[pos]=1e17;
res(u,par[pos]);
}
long long get(int u,int pos){
long long ans=1e17;
if (pos==0)return ans;
ans=min(ans,cal(u,pos)+mxx[pos]);
ans=min(ans,get(u,par[pos]));
return ans;
}*/
long long Query(int S,int X[],int T,int Y[]){
long long ans=1e17;
for (int i=0;i<S;i++){
    for (int j=0;j<T;j++){
        ans=min(ans,cal(X[i],Y[j]));
    }
}
return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 12448 KB Output is correct
2 Execution timed out 8086 ms 30656 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 1457 ms 159160 KB Output is correct
3 Correct 3183 ms 162484 KB Output is correct
4 Correct 987 ms 156428 KB Output is correct
5 Correct 2561 ms 193600 KB Output is correct
6 Correct 2457 ms 164452 KB Output is correct
7 Correct 4320 ms 60620 KB Output is correct
8 Correct 1229 ms 60196 KB Output is correct
9 Correct 4884 ms 65080 KB Output is correct
10 Correct 2692 ms 62132 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 12448 KB Output is correct
2 Execution timed out 8086 ms 30656 KB Time limit exceeded
3 Halted 0 ms 0 KB -