oj.uz

Submission #645456

# Submission time Handle Problem Language Result Execution time Memory
645456 2022-09-27T07:04:48 Z karrigan Factories (JOI14_factories) C++17
33 / 100
 8000 ms 137564 KB 
#include "factories.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct edg{
int v;
long long w;
};
vector<edg>g[500009];
long long dis[500009];
int dep[500009];
int st[500009][19];
int sub[500009];
int use[500009];
void dfs(int u,int par){
    for (auto v:g[u]){
        if (v.v==par)continue;
        dis[v.v]=v.w+dis[u];
        dep[v.v]=dep[u]+1;
        st[v.v][0]=u;
        dfs(v.v,u);
    }
}
inline int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for (int i=18;i>=0;i--){
    if (k>>i&1){
        u=st[u][i];
    }
}
if (u==v)return u;
for (int i=18;i>=0;i--){
    if (st[u][i]==0||st[v][i]==0)continue;
    if (st[u][i]!=st[v][i]){
        u=st[u][i];
        v=st[v][i];
    }
}
return st[u][0];
}
inline long long cal(int u,int v){
return dis[u]+dis[v]-2*dis[lca(u,v)];
}
inline 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];
}
inline 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++){
    a[i]++;
    b[i]++;
    g[a[i]].push_back({b[i],d[i]});
    g[b[i]].push_back({a[i],d[i]});
}
dfs(1,0);
for (int i=1;i<=18;i++){
    for (int j=1;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);
}
long long Query(int s,int x[],int t,int y[]){
for (int i=0;i<t;i++){
    int node=y[i]+1;
    while (node!=0){
        mxx[node]=min(mxx[node],cal(node,y[i]+1));
        node=par[node];
    }
}
long long ans=1e17;
for (int i=0;i<s;i++){
    int node=x[i]+1;
    while (node!=0){
        ans=min(ans,mxx[node]+cal(node,x[i]+1));
        node=par[node];
    }
}
for (int i=0;i<t;i++){
    int node=y[i]+1;
    while (node!=0){
        mxx[node]=1e17;
        node=par[node];
    }
}
return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12452 KB Output is correct
2 Correct 766 ms 20868 KB Output is correct
3 Correct 1402 ms 20916 KB Output is correct
4 Correct 1334 ms 20924 KB Output is correct
5 Correct 1653 ms 21312 KB Output is correct
6 Correct 321 ms 20900 KB Output is correct
7 Correct 1437 ms 20924 KB Output is correct
8 Correct 1459 ms 20952 KB Output is correct
9 Correct 1550 ms 21292 KB Output is correct
10 Correct 325 ms 20936 KB Output is correct
11 Correct 1457 ms 20924 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12244 KB Output is correct
2 Correct 2671 ms 103400 KB Output is correct
3 Correct 5984 ms 107172 KB Output is correct
4 Correct 846 ms 100956 KB Output is correct
5 Correct 7930 ms 137564 KB Output is correct
6 Correct 6557 ms 108600 KB Output is correct
7 Correct 3723 ms 39176 KB Output is correct
8 Correct 605 ms 38744 KB Output is correct
9 Correct 5127 ms 43656 KB Output is correct
10 Correct 4013 ms 40352 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12452 KB Output is correct
2 Correct 766 ms 20868 KB Output is correct
3 Correct 1402 ms 20916 KB Output is correct
4 Correct 1334 ms 20924 KB Output is correct
5 Correct 1653 ms 21312 KB Output is correct
6 Correct 321 ms 20900 KB Output is correct
7 Correct 1437 ms 20924 KB Output is correct
8 Correct 1459 ms 20952 KB Output is correct
9 Correct 1550 ms 21292 KB Output is correct
10 Correct 325 ms 20936 KB Output is correct
11 Correct 1457 ms 20924 KB Output is correct
12 Correct 9 ms 12244 KB Output is correct
13 Correct 2671 ms 103400 KB Output is correct
14 Correct 5984 ms 107172 KB Output is correct
15 Correct 846 ms 100956 KB Output is correct
16 Correct 7930 ms 137564 KB Output is correct
17 Correct 6557 ms 108600 KB Output is correct
18 Correct 3723 ms 39176 KB Output is correct
19 Correct 605 ms 38744 KB Output is correct
20 Correct 5127 ms 43656 KB Output is correct
21 Correct 4013 ms 40352 KB Output is correct
22 Correct 3997 ms 104992 KB Output is correct
23 Correct 3852 ms 107324 KB Output is correct
24 Execution timed out 8026 ms 108900 KB Time limit exceeded
25 Halted 0 ms 0 KB -