oj.uz

Submission #656956

# Submission time Handle Problem Language Result Execution time Memory
656956 2022-11-08T14:32:16 Z bachhoangxuan Factories (JOI14_factories) C++17
100 / 100
 3121 ms 319864 KB 
#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define piii pair<ll,pii>
#define se second
#define fi first
#define maxn 500005
#define maxl 22
const ll inf=1e18;
vector<pii> edge[maxn],adj[maxn];
ll n,q,sz,cnt,len,L[maxn],R[maxn],Min[2*maxn][maxl],cn[2*maxn],f[maxn],lg[2*maxn],dep[maxn];
int scc[maxn];
bool cmp(int a,int b){
    return L[a]<L[b];
}
void dfs(ll u,ll par){
    L[u]=++cnt;len++;
    f[u]=Min[len][0]=len;cn[len]=u;
    for(pii v:edge[u]){
        if(v.first==par) continue;
        dep[v.first]=dep[u]+v.second;
        dfs(v.first,u);
        Min[++len][0]=f[u];
    }
    R[u]=cnt;
}
ll lca(ll u,ll v){
    u=f[u];v=f[v];
    if(u>v) swap(u,v);
    ll p=lg[v-u+1],a=min(Min[u][p],Min[v-(1<<p)+1][p]);
    return cn[a];
}
ll getdist(ll u,ll v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void build_sparse(){
    for(ll i=2;i<=len;i++) lg[i]=lg[i/2]+1;
    for(ll i=1;i<20;i++){
        for(ll j=1;j<=(len-(1<<i)+1);j++) Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]);
    }
}
ll Min1[maxn],Min2[maxn];
void dfs2(int u){
    Min1[u]=Min2[u]=inf;
    for(pii v:adj[u]){
        dfs2(v.first);
        Min1[u]=min(Min1[u],Min1[v.first]+v.second);
        Min2[u]=min(Min2[u],Min2[v.first]+v.second);
    }
    if(scc[u]&1) Min1[u]=0;
    if(scc[u]&2) Min2[u]=0;
}
void redfs(int u,pii dt){
    Min1[u]=min(Min1[u],dt.first);Min2[u]=min(Min2[u],dt.second);
    for(pii v:adj[u]){
        redfs(v.first,{Min1[u]+v.second,Min2[u]+v.second});
    }
}
long long Query(int s,int xs[],int t,int yt[]){
    vector<int> node;
    for(int i=0;i<s;i++){scc[xs[i]+1]+=1;node.push_back(xs[i]+1);}
    for(int i=0;i<t;i++){scc[yt[i]+1]+=2;node.push_back(yt[i]+1);}
    sort(node.begin(),node.end(),cmp);
    for(int i=0;i<(s+t-1);i++) node.push_back(lca(node[i],node[i+1]));
    sort(node.begin(),node.end(),cmp);
    node.erase(unique(node.begin(),node.end()),node.end());
    int root=-1;vector<int> v;
    for(int x:node){
        while(!v.empty() && R[v.back()]<L[x]) v.pop_back();
        if(!v.empty()) adj[v.back()].push_back({x,dep[x]-dep[v.back()]});
        else root=x;
        v.push_back(x);
    }
    dfs2(root);redfs(root,{inf,inf});
    ll res=inf;
    for(int x:node) res=min(res,Min1[x]+Min2[x]);
    for(int x:node){scc[x]=0;adj[x].clear();Min1[x]=Min2[x]=0;}
    return res;
}
void Init(int N, int A[],int B[],int D[]) {
    n=N;
    for(ll i=0;i<n-1;i++){
        edge[A[i]+1].push_back({B[i]+1,D[i]});
        edge[B[i]+1].push_back({A[i]+1,D[i]});
    }
    dfs(1,0);build_sparse();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24368 KB Output is correct
2 Correct 802 ms 35708 KB Output is correct
3 Correct 831 ms 35792 KB Output is correct
4 Correct 832 ms 35900 KB Output is correct
5 Correct 753 ms 36020 KB Output is correct
6 Correct 472 ms 35732 KB Output is correct
7 Correct 767 ms 35760 KB Output is correct
8 Correct 778 ms 35804 KB Output is correct
9 Correct 753 ms 36052 KB Output is correct
10 Correct 482 ms 35648 KB Output is correct
11 Correct 767 ms 35688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24204 KB Output is correct
2 Correct 1426 ms 276408 KB Output is correct
3 Correct 1453 ms 291472 KB Output is correct
4 Correct 1044 ms 277120 KB Output is correct
5 Correct 1519 ms 319332 KB Output is correct
6 Correct 1574 ms 284164 KB Output is correct
7 Correct 1136 ms 88524 KB Output is correct
8 Correct 740 ms 87852 KB Output is correct
9 Correct 1032 ms 94736 KB Output is correct
10 Correct 1114 ms 89932 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24368 KB Output is correct
2 Correct 802 ms 35708 KB Output is correct
3 Correct 831 ms 35792 KB Output is correct
4 Correct 832 ms 35900 KB Output is correct
5 Correct 753 ms 36020 KB Output is correct
6 Correct 472 ms 35732 KB Output is correct
7 Correct 767 ms 35760 KB Output is correct
8 Correct 778 ms 35804 KB Output is correct
9 Correct 753 ms 36052 KB Output is correct
10 Correct 482 ms 35648 KB Output is correct
11 Correct 767 ms 35688 KB Output is correct
12 Correct 14 ms 24204 KB Output is correct
13 Correct 1426 ms 276408 KB Output is correct
14 Correct 1453 ms 291472 KB Output is correct
15 Correct 1044 ms 277120 KB Output is correct
16 Correct 1519 ms 319332 KB Output is correct
17 Correct 1574 ms 284164 KB Output is correct
18 Correct 1136 ms 88524 KB Output is correct
19 Correct 740 ms 87852 KB Output is correct
20 Correct 1032 ms 94736 KB Output is correct
21 Correct 1114 ms 89932 KB Output is correct
22 Correct 2743 ms 288756 KB Output is correct
23 Correct 2327 ms 289764 KB Output is correct
24 Correct 3121 ms 294332 KB Output is correct
25 Correct 2999 ms 296412 KB Output is correct
26 Correct 2570 ms 287312 KB Output is correct
27 Correct 2980 ms 319864 KB Output is correct
28 Correct 1575 ms 284320 KB Output is correct
29 Correct 2457 ms 285732 KB Output is correct
30 Correct 2566 ms 285040 KB Output is correct
31 Correct 2541 ms 285692 KB Output is correct
32 Correct 1705 ms 102476 KB Output is correct
33 Correct 868 ms 96280 KB Output is correct
34 Correct 1358 ms 92632 KB Output is correct
35 Correct 1267 ms 92244 KB Output is correct
36 Correct 1399 ms 93284 KB Output is correct
37 Correct 1360 ms 93108 KB Output is correct