Submission #97333

#	Time	Username	Problem	Language	Result	Execution time	Memory
97333		igzi	Factories (JOI14_factories)	C++17	33 / 100	8026 ms	275616 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];

long long n,d[maxN],s[2*maxN][22],p[maxN],l[2*maxN],dis[maxN],ds[2][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[i][0]=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[i][j]=minimum(s[i][j-1],s[i+(1<<(j-1))][j-1]);
}
}
}

void dfs2(int n,int par){
for(int i=0;i<adj[n].size();i++){
if(adj[n][i].first==par) continue;
dfs2(adj[n][i].first,n);
ds[0][n]=min(ds[0][n],ds[0][adj[n][i].first]+adj[n][i].second);
ds[1][n]=min(ds[1][n],ds[1][adj[n][i].first]+adj[n][i].second);
}
}

long long Query(int S,int x[],int T,int y[]){
if(S*T<=n){
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[a][l[len]],s[b-(1<<l[len])+1][l[len]]);
        ans=min(ans,dis[x[i]]+dis[y[j]]-2*dis[tmp]);
    }
}
return ans;
}
int i;
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;
dfs2(0,-1);
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:15: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:43:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<e.size();i++){
         ~^~~~~~~~~
factories.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<e.size();i++){
         ~^~~~~~~~~
factories.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i+(1<<(j-1))>e.size()) continue;
        ~~~~~~~~~~~~^~~~~~~~~
factories.cpp: In function 'void dfs2(int, int)':
factories.cpp:59:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i=0;i<adj[n].size();i++){
             ~^~~~~~~~~~~~~~

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