Submission #110720

#	Time	Username	Problem	Language	Result	Execution time	Memory
110720		autumn_eel	Factories (JOI14_factories)	C++14	33 / 100	4469 ms	241396 KiB

factories

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;

#include "factories.h"


struct Segtree{
	int N;
	vector<P>dat;
	Segtree(){}
	Segtree(vector<P>v){
		N=1;while(N<v.size())N<<=1;
		dat=vector<P>(2*N);
		for(int i=2*N-1;i>=1;i--){
			if(i>=N){
				if(i-N>=v.size())dat[i]=P(INF,-1);
				else dat[i]=v[i-N];
			}
			else dat[i]=min(dat[i*2],dat[i*2+1]);
		}
	}
	int query(int l,int r){
		l+=N;r+=N;
		P res(INF,-1);
		while(l<r){
			if(l&1)res=min(res,dat[l++]);
			if(r&1)res=min(res,dat[--r]);
			l>>=1;
			r>>=1;
		}
		return res.second;
	}
};

int n;
vector<P>E[600000];
int vid[600000];
vector<P>vs;
ll d[600000],depth[600000];
Segtree seg;

void dfs(int v,int p,ll dep){
	depth[v]=dep;
	vid[v]=vs.size();
	vs.push_back(P(depth[v],v));
	for(auto u:E[v]){
		if(u.second==p)continue;
		dfs(u.second,v,dep+u.first);
		vs.push_back(P(depth[v],v));
	}
}

int lca(int u,int v){
	return seg.query(min(vid[u],vid[v]),max(vid[u],vid[v])+1);
}

ll dist(int u,int v){
	int p=lca(u,v);
	return depth[u]+depth[v]-depth[p]*2;
}

void Init(int N, int A[], int B[], int D[]) {
	n=N;
	rep(i,n-1){
		E[A[i]].push_back(P(D[i],B[i]));
		E[B[i]].push_back(P(D[i],A[i]));
	}
	dfs(0,-1,0);
	seg=Segtree(vs);
}


long long Query(int S, int X[], int T, int Y[]) {
	if(S<=20&&T<=20){
		ll Min=INF;
		rep(i,S)rep(j,T){
			Min=min(Min,dist(X[i],Y[j]));
		}
		return Min;
	}
	if(n<=5000){
		priority_queue<P,vector<P>,greater<P>>que;
		rep(i,n)d[i]=INF;
		rep(i,S){
			d[X[i]]=0;
			que.push(P(0,X[i]));
		}
		while(!que.empty()){
			P p=que.top();que.pop();
			if(d[p.second]!=p.first)continue;
			for(P u:E[p.second]){
				if(d[u.second]>p.first+u.first){
					d[u.second]=p.first+u.first;
					que.push(P(d[u.second],u.second));
				}
			}
		}
		ll Min=INF;
		rep(i,T)Min=min(Min,d[Y[i]]);
		return Min;
	}
	abort();
}

Compilation message (stderr)

factories.cpp: In constructor 'Segtree::Segtree(std::vector<std::pair<long long int, int> >)':
factories.cpp:16:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   N=1;while(N<v.size())N<<=1;
             ~^~~~~~~~~
factories.cpp:20:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i-N>=v.size())dat[i]=P(INF,-1);
        ~~~^~~~~~~~~~

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