oj.uz

Submission #645454

# Submission time Handle Problem Language Result Execution time Memory
645454 2022-09-27T07:01:11 Z karrigan Factories (JOI14_factories) C++14
33 / 100
 8000 ms 137608 KB 
#include "factories.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const long long mx=1e15;
struct edg{
int v;
long long w;
};
vector<edg>g[500001];
long long dis[500001];
int dep[500001];
int st[500001][19];
int sub[500001];
int use[500001];
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[500001];
long long mxx[500001];
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);
}
inline void update(int u,int pos){
if (pos==0)return;
mxx[pos]=min(mxx[pos],cal(u,pos));
update(u,par[pos]);
}
inline void res(int u,int pos){
if (pos==0)return;
mxx[pos]=1e17;
res(u,par[pos]);
}
inline 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[]){
for (int i=0;i<t;i++){
    update(y[i]+1,y[i]+1);
}
long long ans=1e17;
for (int i=0;i<s;i++){
    ans=min(ans,get(x[i]+1,x[i]+1));
}
for (int i=0;i<t;i++){
    res(y[i]+1,y[i]+1);
}
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 683 ms 20864 KB Output is correct
3 Correct 1336 ms 20896 KB Output is correct
4 Correct 1304 ms 21164 KB Output is correct
5 Correct 1420 ms 21332 KB Output is correct
6 Correct 279 ms 20940 KB Output is correct
7 Correct 1332 ms 21100 KB Output is correct
8 Correct 1398 ms 21264 KB Output is correct
9 Correct 1432 ms 21276 KB Output is correct
10 Correct 292 ms 21080 KB Output is correct
11 Correct 1335 ms 21028 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 2414 ms 103256 KB Output is correct
3 Correct 5299 ms 107252 KB Output is correct
4 Correct 725 ms 101088 KB Output is correct
5 Correct 7108 ms 137608 KB Output is correct
6 Correct 5796 ms 108552 KB Output is correct
7 Correct 3671 ms 39348 KB Output is correct
8 Correct 494 ms 38796 KB Output is correct
9 Correct 4379 ms 43800 KB Output is correct
10 Correct 3711 ms 40612 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 683 ms 20864 KB Output is correct
3 Correct 1336 ms 20896 KB Output is correct
4 Correct 1304 ms 21164 KB Output is correct
5 Correct 1420 ms 21332 KB Output is correct
6 Correct 279 ms 20940 KB Output is correct
7 Correct 1332 ms 21100 KB Output is correct
8 Correct 1398 ms 21264 KB Output is correct
9 Correct 1432 ms 21276 KB Output is correct
10 Correct 292 ms 21080 KB Output is correct
11 Correct 1335 ms 21028 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 2414 ms 103256 KB Output is correct
14 Correct 5299 ms 107252 KB Output is correct
15 Correct 725 ms 101088 KB Output is correct
16 Correct 7108 ms 137608 KB Output is correct
17 Correct 5796 ms 108552 KB Output is correct
18 Correct 3671 ms 39348 KB Output is correct
19 Correct 494 ms 38796 KB Output is correct
20 Correct 4379 ms 43800 KB Output is correct
21 Correct 3711 ms 40612 KB Output is correct
22 Correct 3630 ms 104856 KB Output is correct
23 Correct 3650 ms 107308 KB Output is correct
24 Execution timed out 8053 ms 108928 KB Time limit exceeded
25 Halted 0 ms 0 KB -