Submission #621256

#	Time	Username	Problem	Language	Result	Execution time	Memory
621256		AbdelmagedNour	Factories (JOI14_factories)	C++17	0 / 100	2088 ms	144512 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];
vector<vector<pair<int,long long>>>adj,adj2;
struct node{
    long long ans,blue,red;
    node(){
        ans=LLONG_MAX;
        blue=red=INT_MAX;
    }
    node(long long a,long long b,long long c){
        ans=a;red=b;blue=c;
    }
};
node Merge(node&par,node&ch){
    long long ans,red,blue;
    ans=min({par.ans,ch.ans,par.blue+ch.red,par.red+ch.blue});
    red=min(par.red,ch.red);
    blue=min(par.blue,ch.blue);
    return node(ans,red,blue);
}
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;
}
node dfs2(int v,int par,map<int,int>&mp){
    node cur=node();
    if(mp[v]==1)cur.red=0;
    else if(mp[v]==2)cur.blue=0;
    for(auto&[u,w]:adj2[v]){
        if(u==par)continue;
        node New=dfs2(u,v,mp);
        New.red+=w;
        New.blue+=w;
        cur=Merge(cur,New);
    }
    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=1;i<temp_sz;i++)v.push_back(LCA(v[i],v[i-1]));
    v.push_back(LCA(v[0],v[temp_sz-1]));
    sort(v.begin(),v.end(),[&](int i,int j){
            return st[i]<st[j];
        });
    v.resize(unique(v.begin(),v.end())-v.begin());
    for(int i=0;i<v.size();i++)adj2[v[i]].clear();
    vector<int>Stack;
    long long res=LLONG_MAX;
    for(int i=0;i<v.size();i++){
        while(!Stack.empty()&&!is_ancestor(Stack.back(),v[i]))Stack.pop_back();
        if(!Stack.empty()){
            int 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]);
    }
    return dfs2(v[0],v[0],mp).ans;
}

Compilation message (stderr)

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

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