oj.uz

Submission #645455

# Submission time Handle Problem Language Result Execution time Memory
645455 2022-09-27T07:04:33 Z karrigan Factories (JOI14_factories) C++14
33 / 100
 8000 ms 137652 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 12372 KB Output is correct
2 Correct 711 ms 20996 KB Output is correct
3 Correct 1378 ms 21044 KB Output is correct
4 Correct 1328 ms 21040 KB Output is correct
5 Correct 1485 ms 21328 KB Output is correct
6 Correct 301 ms 20900 KB Output is correct
7 Correct 1382 ms 20916 KB Output is correct
8 Correct 1397 ms 21164 KB Output is correct
9 Correct 1454 ms 21384 KB Output is correct
10 Correct 298 ms 20876 KB Output is correct
11 Correct 1361 ms 20940 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 2739 ms 103224 KB Output is correct
3 Correct 5674 ms 107392 KB Output is correct
4 Correct 860 ms 100960 KB Output is correct
5 Correct 7555 ms 137652 KB Output is correct
6 Correct 6071 ms 108460 KB Output is correct
7 Correct 3717 ms 39168 KB Output is correct
8 Correct 545 ms 38760 KB Output is correct
9 Correct 4869 ms 43672 KB Output is correct
10 Correct 4000 ms 40448 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12372 KB Output is correct
2 Correct 711 ms 20996 KB Output is correct
3 Correct 1378 ms 21044 KB Output is correct
4 Correct 1328 ms 21040 KB Output is correct
5 Correct 1485 ms 21328 KB Output is correct
6 Correct 301 ms 20900 KB Output is correct
7 Correct 1382 ms 20916 KB Output is correct
8 Correct 1397 ms 21164 KB Output is correct
9 Correct 1454 ms 21384 KB Output is correct
10 Correct 298 ms 20876 KB Output is correct
11 Correct 1361 ms 20940 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 2739 ms 103224 KB Output is correct
14 Correct 5674 ms 107392 KB Output is correct
15 Correct 860 ms 100960 KB Output is correct
16 Correct 7555 ms 137652 KB Output is correct
17 Correct 6071 ms 108460 KB Output is correct
18 Correct 3717 ms 39168 KB Output is correct
19 Correct 545 ms 38760 KB Output is correct
20 Correct 4869 ms 43672 KB Output is correct
21 Correct 4000 ms 40448 KB Output is correct
22 Correct 4003 ms 104864 KB Output is correct
23 Correct 4307 ms 107184 KB Output is correct
24 Execution timed out 8009 ms 108900 KB Time limit exceeded
25 Halted 0 ms 0 KB -