Submission #621265

#	Time	Username	Problem	Language	Result	Execution time	Memory
621265		AbdelmagedNour	Factories (JOI14_factories)	C++17	100 / 100	5221 ms	161520 KiB

factories

#include<bits/stdc++.h>
using namespace std;
#include "factories.h"
const int MAXN=500005;
int st[MAXN],en[MAXN],p[MAXN][20],id;
long long dis[MAXN],ans,INF=1e18;
vector<vector<pair<int,long long>>>adj,adj2;

void dfs(int v,int par=0,long long dist=0){
    st[v]=++id;
    p[v][0]=par;
    dis[v]=dist;
    for(int i=1;i<20;i++)p[v][i]=p[p[v][i-1]][i-1];
    for(auto&[u,w]:adj[v]){
        if(u==par)continue;
        dfs(u,v,dist+w);
    }
    en[v]=id;
}
pair<long long,long long>solve(int v,int par,map<int,int>&mp){
    pair<long long,long long>cur=make_pair(INF, INF);
    if(mp[v]==1)cur.first=0;
    if(mp[v]==2)cur.second=0;
    for(auto[u,w]:adj2[v]){
        if(u==par)continue;
        auto f=solve(u,v,mp);
        f.first+=w;
        f.second+=w;
        ans=min(ans,cur.first+f.second);
        ans=min(ans,cur.second+f.first);
        cur.first=min(cur.first,f.first);
        cur.second=min(cur.second,f.second);
    }
    return cur;
}
bool is_ancestor(int u,int v){
    return st[u]<=st[v]&&en[u]>=en[v];
}
int LCA(int u,int v){
    if(is_ancestor(u,v))return u;
    if(is_ancestor(v,u))return v;
    for(int i=19;i>=0;i--){
        if(is_ancestor(p[u][i],v))continue;
        u=p[u][i];
    }
    return p[u][0];
}
long long cost(int u,int v){
    return dis[u]+dis[v]-2*dis[LCA(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
    id=-1;
    adj.resize(N);
    adj2.resize(N);
    for(int i=0;i<N-1;i++){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    dfs(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    map<int,int>mp;
    vector<int>v;
    for(int i=0;i<S;i++){
        mp[X[i]]=1;
        v.push_back(X[i]);
    }
    for(int i=0;i<T;i++){
        mp[Y[i]]=2;
        v.push_back(Y[i]);
    }
    sort(v.begin(),v.end(),[&](int i,int j){
            return st[i]<st[j];
        });
    int temp_sz=v.size();
    for(int i=0;i<temp_sz;i++){
        v.push_back(LCA(v[i],v[(i+1)%temp_sz]));
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    sort(v.begin(),v.end(),[&](int i,int j){
            return st[i]<st[j];
        });
    for(int i=0;i<v.size();i++)adj2[v[i]].clear();
    vector<int>Stack;
    for(int i=0;i<v.size();i++){
        while(!Stack.empty()&&!is_ancestor(Stack.back(),v[i]))Stack.pop_back();
        if(!Stack.empty()){
            long long U=Stack.back(),V=v[i],C=cost(U,V);
            adj2[U].push_back({V,C});
            adj2[V].push_back({U,C});
        }
        Stack.push_back(v[i]);
    }
    ans=LLONG_MAX;
    solve(v[0],-1,mp);
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<v.size();i++)adj2[v[i]].clear();
      |                 ~^~~~~~~~~
factories.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67