oj.uz

Submission #645457

# Submission time Handle Problem Language Result Execution time Memory
645457 2022-09-27T07:06:16 Z karrigan Factories (JOI14_factories) C++17
33 / 100
 8000 ms 137616 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);
    }
}
long long cal(int u,int v){
long long sum=dis[u]+dis[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 sum-2*dis[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 sum-2*dis[st[u][0]];
}
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++){
    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 21 ms 12372 KB Output is correct
2 Correct 729 ms 20868 KB Output is correct
3 Correct 1426 ms 21016 KB Output is correct
4 Correct 1361 ms 20904 KB Output is correct
5 Correct 1467 ms 21388 KB Output is correct
6 Correct 271 ms 20900 KB Output is correct
7 Correct 1322 ms 20900 KB Output is correct
8 Correct 1451 ms 20924 KB Output is correct
9 Correct 1488 ms 21384 KB Output is correct
10 Correct 267 ms 20892 KB Output is correct
11 Correct 1326 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 2521 ms 103284 KB Output is correct
3 Correct 5398 ms 107328 KB Output is correct
4 Correct 766 ms 100996 KB Output is correct
5 Correct 7401 ms 137616 KB Output is correct
6 Correct 5725 ms 108568 KB Output is correct
7 Correct 3587 ms 39284 KB Output is correct
8 Correct 524 ms 38884 KB Output is correct
9 Correct 4868 ms 43724 KB Output is correct
10 Correct 3982 ms 40484 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 12372 KB Output is correct
2 Correct 729 ms 20868 KB Output is correct
3 Correct 1426 ms 21016 KB Output is correct
4 Correct 1361 ms 20904 KB Output is correct
5 Correct 1467 ms 21388 KB Output is correct
6 Correct 271 ms 20900 KB Output is correct
7 Correct 1322 ms 20900 KB Output is correct
8 Correct 1451 ms 20924 KB Output is correct
9 Correct 1488 ms 21384 KB Output is correct
10 Correct 267 ms 20892 KB Output is correct
11 Correct 1326 ms 20940 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 2521 ms 103284 KB Output is correct
14 Correct 5398 ms 107328 KB Output is correct
15 Correct 766 ms 100996 KB Output is correct
16 Correct 7401 ms 137616 KB Output is correct
17 Correct 5725 ms 108568 KB Output is correct
18 Correct 3587 ms 39284 KB Output is correct
19 Correct 524 ms 38884 KB Output is correct
20 Correct 4868 ms 43724 KB Output is correct
21 Correct 3982 ms 40484 KB Output is correct
22 Correct 3788 ms 104940 KB Output is correct
23 Correct 4002 ms 107196 KB Output is correct
24 Execution timed out 8047 ms 108936 KB Time limit exceeded
25 Halted 0 ms 0 KB -