Submission #97399

#	Time	Username	Problem	Language	Result	Execution time	Memory
97399		igzi	Factories (JOI14_factories)	C++17	0 / 100	37 ms	12664 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],p[maxN],pos[maxN],l[2*maxN],dis[maxN],ds[2][maxN];
int s[22][2*maxN],sx[22][maxN],sy[22][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;
pos[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)>e.size()) continue;
    s[j][i]=minimum(s[j-1][i],s[j-1][i+(1<<(j-1))]);
}
}
}

int minimum2(int a,int b){
if(dis[a]<dis[b]) return a;
return b;
}

long long Query(int S,int x[],int T,int y[]){
long long ans=INF;
vector <int> lca,v,X,Y;
int i,j,a,b,tmp,len,pom;
for(i=0;i<S;i++) {v.push_back(p[x[i]]); X.push_back(p[x[i]]);}
for(i=0;i<T;i++) {v.push_back(p[y[i]]); Y.push_back(p[y[i]]);}
sort(v.begin(),v.end());
sort(X.begin(),X.end());
sort(X.begin(),X.end());
for(i=1;i<v.size();i++){
    a=v[i-1];
    b=v[i];
    len=b-a+1;
    tmp=minimum(s[l[len]][a],s[l[len]][b-(1<<l[len])+1]);
    lca.push_back(tmp);
}
for(i=0;i<S;i++){
sx[0][i]=e[X[i]];
}
for(j=1;(1<<j)<=S;j++){
for(i=0;i<S;i++){
    if(i+(1<<j)>S) continue;
    sx[j][i]=minimum2(sx[j-1][i],sx[j-1][i+(1<<(j-1))]);
}
}
for(i=0;i<T;i++){
sy[0][i]=e[Y[i]];
}
for(j=1;(1<<j)<=T;j++){
for(i=0;i<T;i++){
    if(i+(1<<j)>T) continue;
    sy[j][i]=minimum2(sy[j-1][i],sy[j-1][i+(1<<(j-1))]);
}
}
for(i=0;i<lca.size();i++){
    a=lower_bound(X.begin(),X.end(),p[lca[i]])-X.begin();
    b=lower_bound(X.begin(),X.end(),pos[lca[i]])-X.begin()-1;
    if(b<a) continue;
    len=b-a+1;
    tmp=minimum(sx[l[len]][a],sx[l[len]][b-(1<<l[len])+1]);
    a=lower_bound(Y.begin(),Y.end(),p[lca[i]])-Y.begin();
    b=lower_bound(Y.begin(),Y.end(),pos[lca[i]])-Y.begin()-1;
    if(b<a) continue;
    len=b-a+1;
    pom=minimum(sy[l[len]][a],sy[l[len]][b-(1<<l[len])+1]);
    ans=min(ans,dis[tmp]+dis[pom]-2*dis[lca[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:53:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<e.size();i++){
         ~^~~~~~~~~
factories.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i+(1<<j)>e.size()) continue;
        ~~~~~~~~^~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:74:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=1;i<v.size();i++){
         ~^~~~~~~~~
factories.cpp:99:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<lca.size();i++){
         ~^~~~~~~~~~~

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