oj.uz

Submission #645452

# Submission time Handle Problem Language Result Execution time Memory
645452 2022-09-27T06:57:54 Z karrigan Factories (JOI14_factories) C++14
33 / 100
 8000 ms 141540 KB 
#include "factories.h"
#include<bits/stdc++.h>
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][21];
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);
    }
}
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]==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];
}
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[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<=20;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);
}
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[]){
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 22 ms 12380 KB Output is correct
2 Correct 751 ms 21040 KB Output is correct
3 Correct 1427 ms 30676 KB Output is correct
4 Correct 1425 ms 30548 KB Output is correct
5 Correct 1479 ms 30940 KB Output is correct
6 Correct 286 ms 30396 KB Output is correct
7 Correct 1399 ms 30580 KB Output is correct
8 Correct 1472 ms 30556 KB Output is correct
9 Correct 1474 ms 30756 KB Output is correct
10 Correct 279 ms 30372 KB Output is correct
11 Correct 1405 ms 30568 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 2588 ms 107276 KB Output is correct
3 Correct 5537 ms 111188 KB Output is correct
4 Correct 808 ms 104952 KB Output is correct
5 Correct 7874 ms 141540 KB Output is correct
6 Correct 6013 ms 112444 KB Output is correct
7 Correct 3814 ms 39960 KB Output is correct
8 Correct 502 ms 39608 KB Output is correct
9 Correct 4634 ms 44756 KB Output is correct
10 Correct 3817 ms 41540 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12380 KB Output is correct
2 Correct 751 ms 21040 KB Output is correct
3 Correct 1427 ms 30676 KB Output is correct
4 Correct 1425 ms 30548 KB Output is correct
5 Correct 1479 ms 30940 KB Output is correct
6 Correct 286 ms 30396 KB Output is correct
7 Correct 1399 ms 30580 KB Output is correct
8 Correct 1472 ms 30556 KB Output is correct
9 Correct 1474 ms 30756 KB Output is correct
10 Correct 279 ms 30372 KB Output is correct
11 Correct 1405 ms 30568 KB Output is correct
12 Correct 8 ms 12244 KB Output is correct
13 Correct 2588 ms 107276 KB Output is correct
14 Correct 5537 ms 111188 KB Output is correct
15 Correct 808 ms 104952 KB Output is correct
16 Correct 7874 ms 141540 KB Output is correct
17 Correct 6013 ms 112444 KB Output is correct
18 Correct 3814 ms 39960 KB Output is correct
19 Correct 502 ms 39608 KB Output is correct
20 Correct 4634 ms 44756 KB Output is correct
21 Correct 3817 ms 41540 KB Output is correct
22 Correct 3863 ms 133020 KB Output is correct
23 Correct 3834 ms 135700 KB Output is correct
24 Execution timed out 8055 ms 136984 KB Time limit exceeded
25 Halted 0 ms 0 KB -