Submission #97367

#	Time	Username	Problem	Language	Result	Execution time	Memory
97367		igzi	Factories (JOI14_factories)	C++17	33 / 100	8077 ms	154964 KiB

factories

#include <bits/stdc++.h>
#define INF 100000000000000000
#include "factories.h"
#define maxN 500005
 
using namespace std;
 
vector <int> e;
vector <pair<int,int>> adj[maxN];
 
int n,d[maxN],s[22][2*maxN],p[maxN],l[2*maxN];
long long ds[2][maxN],dis[maxN];
 
void dfs(int n,int par){
e.push_back(n);
for(int i=0;i<adj[n].size();i++){
if(adj[n][i].first==par) continue;
dis[adj[n][i].first]=dis[n]+adj[n][i].second;
d[adj[n][i].first]=d[n]+1;
dfs(adj[n][i].first,n);
e.push_back(n);
}
}
 
int minimum(int a,int b){
if(d[a]<d[b]) return a;
return b;
}
 
void Init(int N,int a[],int b[],int D[]){
n=N;
int i,j;
for(i=0;i<n-1;i++){
adj[a[i]].push_back({b[i],D[i]});
adj[b[i]].push_back({a[i],D[i]});
}
d[0]=0;
dis[0]=0;
dfs(0,-1);
l[1]=0;
for(i=0;i<n;i++){
p[i]=-1;
}
for(i=0;i<e.size();i++){
if(p[e[i]]==-1) p[e[i]]=i;
s[0][i]=e[i];
if(i<2) continue;
if(i==(i & -i)) l[i]=l[i-1]+1;
else l[i]=l[i-1];
}
for(j=1;j<21;j++){
for(i=0;i<e.size();i++){
    if(i+(1<<(j-1))>e.size()) continue;
    s[j][i]=minimum(s[j-1][i],s[j-1][i+(1<<(j-1))]);
}
}
}
 
long long Query(int S,int x[],int T,int y[]){
if(S*T<=2*n/3){
int i,j,tmp,a,b,len;
long long ans=INF;
for(i=0;i<S;i++){
    for(j=0;j<T;j++){
        a=min(p[x[i]],p[y[j]]);
        b=max(p[x[i]],p[y[j]]);
        len=b-a+1;
        tmp=minimum(s[l[len]][a],s[l[len]][b-(1<<l[len])+1]);
        ans=min(ans,dis[x[i]]+dis[y[j]]-2*dis[tmp]);
    }
}
return ans;
}
int i,j;
long long ans=INF;
for(i=0;i<n;i++) ds[0][i]=ds[1][i]=INF;
for(i=0;i<S;i++) ds[0][x[i]]=0;
for(i=0;i<T;i++) ds[1][y[i]]=0;
for(i=e.size()-1;i>=0;i--){
if(p[e[i]]!=i) continue;
for(j=0;j<adj[e[i]].size();j++){
if(p[adj[e[i]][j].first]<i) continue;
ds[0][e[i]]=min(ds[0][e[i]],ds[0][adj[e[i]][j].first]+adj[e[i]][j].second);
ds[1][e[i]]=min(ds[1][e[i]],ds[1][adj[e[i]][j].first]+adj[e[i]][j].second);
}
}
for(i=0;i<n;i++) ans=min(ans,ds[0][i]+ds[1][i]);
return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:16:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:44:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<e.size();i++){
         ~^~~~~~~~~
factories.cpp:52:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<e.size();i++){
         ~^~~~~~~~~
factories.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i+(1<<(j-1))>e.size()) continue;
        ~~~~~~~~~~~~^~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:81:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(j=0;j<adj[e[i]].size();j++){
         ~^~~~~~~~~~~~~~~~~

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