oj.uz

Submission #645475

# Submission time Handle Problem Language Result Execution time Memory
645475 2022-09-27T08:13:49 Z karrigan Factories (JOI14_factories) C++14
100 / 100
 6348 ms 192744 KB 
#include "factories.h"
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
struct edg{
int v;
long long w;
};
vector<edg>g[500009];
vector<edg>lon[500009];
long long dis[500009];
int dep[500009];
int st[500009][21];
int sub[500009];
int use[500009];
int in[500009];
int ck[500009];
int cnt=0;
bool cmp(int i,int j){
return in[i]<in[j];
}
void dfs(int u,int par){
    in[u]=++cnt;
    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)];
}
long long cac[500009];//min 1
long long buoi[500009];//min 2
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++){
        cac[j]=buoi[j]=1e17;
        st[j][i]=st[st[j][i-1]][i-1];
    }
}
}
long long ans=1e17;
void redfs(int u){
    if (use[u]==1)cac[u]=0;
    if (use[u]==2)buoi[u]=0;
    for (auto v:lon[u]){
        redfs(v.v);
        cac[u]=min(cac[u],cac[v.v]+v.w);
        buoi[u]=min(buoi[u],buoi[v.v]+v.w);
    }
    ans=min(ans,cac[u]+buoi[u]);
}
long long Query(int s,int x[],int t,int y[]){
vector<int>tp;
for (int i=0;i<s;i++){
    use[x[i]+1]=1;
    ck[x[i]+1]=1;
    tp.push_back(x[i]+1);
}
for (int i=0;i<t;i++){
    use[y[i]+1]=2;
    ck[y[i]+1]=1;
    tp.push_back(y[i]+1);
}
sort(tp.begin(),tp.end(),cmp);
for (int i=1;i<(int)tp.size();i++){
    int u=tp[i],v=tp[i-1];
    if (ck[lca(u,v)]==0){
        ck[lca(u,v)]=1;
        tp.push_back(lca(u,v));
    }
}
sort(tp.begin(),tp.end(),cmp);
vector<int>dit;
for (auto v:tp){
    if (dit.empty()){
        dit.push_back(v);
    }
    else {
        while (!dit.empty()&&lca(dit.back(),v)!=dit.back())dit.pop_back();
        lon[dit.back()].push_back({v,cal(dit.back(),v)});
        dit.push_back(v);
    }
}
ans=1e17;
redfs(dit[0]);
for (auto v:tp){
    ck[v]=0;
    lon[v].clear();
    cac[v]=buoi[v]=1e17;
}
for (int i=0;i<s;i++){
    use[x[i]+1]=0;
}
for (int i=0;i<t;i++){
    use[y[i]+1]=0;
}
return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 24148 KB Output is correct
2 Correct 1249 ms 32904 KB Output is correct
3 Correct 1541 ms 33016 KB Output is correct
4 Correct 1332 ms 33068 KB Output is correct
5 Correct 1047 ms 33264 KB Output is correct
6 Correct 940 ms 32972 KB Output is correct
7 Correct 1546 ms 32932 KB Output is correct
8 Correct 1639 ms 32992 KB Output is correct
9 Correct 1088 ms 33268 KB Output is correct
10 Correct 1050 ms 32976 KB Output is correct
11 Correct 1661 ms 32916 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24024 KB Output is correct
2 Correct 2377 ms 123064 KB Output is correct
3 Correct 3590 ms 128300 KB Output is correct
4 Correct 1564 ms 120660 KB Output is correct
5 Correct 2991 ms 168564 KB Output is correct
6 Correct 3894 ms 129588 KB Output is correct
7 Correct 3613 ms 52956 KB Output is correct
8 Correct 1541 ms 52144 KB Output is correct
9 Correct 2623 ms 59856 KB Output is correct
10 Correct 3363 ms 54248 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 24148 KB Output is correct
2 Correct 1249 ms 32904 KB Output is correct
3 Correct 1541 ms 33016 KB Output is correct
4 Correct 1332 ms 33068 KB Output is correct
5 Correct 1047 ms 33264 KB Output is correct
6 Correct 940 ms 32972 KB Output is correct
7 Correct 1546 ms 32932 KB Output is correct
8 Correct 1639 ms 32992 KB Output is correct
9 Correct 1088 ms 33268 KB Output is correct
10 Correct 1050 ms 32976 KB Output is correct
11 Correct 1661 ms 32916 KB Output is correct
12 Correct 18 ms 24024 KB Output is correct
13 Correct 2377 ms 123064 KB Output is correct
14 Correct 3590 ms 128300 KB Output is correct
15 Correct 1564 ms 120660 KB Output is correct
16 Correct 2991 ms 168564 KB Output is correct
17 Correct 3894 ms 129588 KB Output is correct
18 Correct 3613 ms 52956 KB Output is correct
19 Correct 1541 ms 52144 KB Output is correct
20 Correct 2623 ms 59856 KB Output is correct
21 Correct 3363 ms 54248 KB Output is correct
22 Correct 3912 ms 133508 KB Output is correct
23 Correct 3937 ms 134288 KB Output is correct
24 Correct 4874 ms 138620 KB Output is correct
25 Correct 5145 ms 165964 KB Output is correct
26 Correct 6096 ms 156364 KB Output is correct
27 Correct 4228 ms 192744 KB Output is correct
28 Correct 2417 ms 153092 KB Output is correct
29 Correct 6348 ms 155236 KB Output is correct
30 Correct 6136 ms 154284 KB Output is correct
31 Correct 6171 ms 154936 KB Output is correct
32 Correct 2258 ms 75472 KB Output is correct
33 Correct 1623 ms 68756 KB Output is correct
34 Correct 2454 ms 65440 KB Output is correct
35 Correct 2367 ms 65288 KB Output is correct
36 Correct 3400 ms 66224 KB Output is correct
37 Correct 3440 ms 66216 KB Output is correct