Submission #114927

#	Time	Username	Problem	Language	Result	Execution time	Memory
114927		Dormi	Factories (JOI14_factories)	C++11	100 / 100	4788 ms	195528 KiB

factories

#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,mmx,popcnt,tune=native"

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
struct pa{
	int dest;
	long long dist;
	pa(int a=0, long long b=0):dest(a),dist(b){}
};
struct tri{
	int dest,parent;
	long long dist;
	tri(int a=0, long long b=0, int c=0):dest(a),dist(b),parent(c){}
};
vector<pa> matrix[500001];
int matrix2[500001];
long long ancdist[500001][19];
int ancri[500001];
bool cent[500001];
int subtreesize[500001];
long long dist[500001];
int rev[500001];
int revri;
long long mi2;
int cur2;
int loc2;
tri st[500001];
int sts=500001;
inline void dfssize(int loc, int parent){
	subtreesize[loc]=1;
	for(pa x:matrix[loc]){
		if(parent^x.dest&&!cent[x.dest]){
			dfssize(x.dest,loc);
			subtreesize[loc]+=subtreesize[x.dest];
		}
	}
}
inline int decompsubtree(int loc, int parent, int size){
	for(pa x:matrix[loc]){
		if(x.dest^parent&&!cent[x.dest]&&subtreesize[x.dest]>size){
			return decompsubtree(x.dest,loc,size);
		}
	}
	return loc;
}
inline int decompfulltree(int loc){
	dfssize(loc,-1);
	if(subtreesize[loc]==1){
		cent[loc]=true;
		ancri[loc]++;
		return loc;
	}
	int next=decompsubtree(loc,-1,subtreesize[loc]/2);
	cent[next]=true;
	st[--sts]=tri(next,0,-1);
	while(sts<=500000){
		tri cur=st[sts++];
		ancdist[cur.dest][ancri[cur.dest]++]=cur.dist;
		for(pa x:matrix[cur.dest]){
			if(x.dest^cur.parent&&!cent[x.dest]){
				st[--sts]=tri(x.dest,cur.dist+x.dist,cur.dest);
			}
		}
	}
	for(pa x:matrix[next]){
		if(!cent[x.dest]){
			matrix2[decompfulltree(x.dest)]=next;
		}
	}
	return next;
}
void Init(int N, int A[], int B[], int D[]){
	for(int i=0;i<N-1;i++){
		matrix[A[i]].push_back(pa(B[i],(long long)D[i]));
		matrix[B[i]].push_back(pa(A[i],(long long)D[i]));
	}
	decompfulltree(1);
	memset(dist,-1,sizeof(dist));
}
long long Query(int S, int X[], int T, int Y[]){
	mi2=LLONG_MAX;
	if(S<T){
		for(int i=0;i<S;i++){
			cur2=X[i];
			loc2=X[i];
			for(int ind=ancri[loc2]-1;ind>=0;ind--) {
				if (dist[loc2]^-1) {
					dist[loc2] = min(dist[loc2], ancdist[cur2][ind]);
				} else {
					rev[revri++]=loc2;
					dist[loc2] = ancdist[cur2][ind];
				}
				loc2 = matrix2[loc2];
			}
		}
		for(int i=0;i<T;i++){
			cur2=Y[i];
			loc2=Y[i];
			for(int ind=ancri[loc2]-1;ind>=0;ind--) {
				if(dist[loc2]^-1) {
					mi2 = min(mi2, ancdist[cur2][ind]+ dist[loc2]);
				}
				loc2 = matrix2[loc2];
			}
		}
	}
	else{
		for(int i=0;i<T;i++){
			cur2=Y[i];
			loc2=Y[i];
			for(int ind=ancri[loc2]-1;ind>=0;ind--) {
				if (dist[loc2]^-1) {
					dist[loc2] = min(dist[loc2], ancdist[cur2][ind]);
				} else {
					rev[revri++]=loc2;
					dist[loc2] = ancdist[cur2][ind];
				}
				loc2 = matrix2[loc2];
			}
		}
		for(int i=0;i<S;i++){
			cur2=X[i];
			loc2=X[i];
			for(int ind=ancri[loc2]-1;ind>=0;ind--) {
				if(dist[loc2]^-1) {
					mi2 = min(mi2, ancdist[cur2][ind]+ dist[loc2]);
				}
				loc2 = matrix2[loc2];
			}
		}
	}
	for(;revri>=0;revri--){
		dist[rev[revri]]=-1;
	}
	revri++;
	return mi2;
}

Compilation message (stderr)

factories.cpp: In constructor 'tri::tri(int, long long int, int)':
factories.cpp:15:12: warning: 'tri::dist' will be initialized after [-Wreorder]
  long long dist;
            ^~~~
factories.cpp:14:11: warning:   'int tri::parent' [-Wreorder]
  int dest,parent;
           ^~~~~~
factories.cpp:16:2: warning:   when initialized here [-Wreorder]
  tri(int a=0, long long b=0, int c=0):dest(a),dist(b),parent(c){}
  ^~~

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