oj.uz

Submission #114927

# Submission time Handle Problem Language Result Execution time Memory
114927 2019-06-04T03:26:44 Z Dormi Factories (JOI14_factories) C++11
100 / 100
 4788 ms 195528 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24568 KB Output is correct
2 Correct 306 ms 42488 KB Output is correct
3 Correct 336 ms 42708 KB Output is correct
4 Correct 329 ms 42556 KB Output is correct
5 Correct 331 ms 42820 KB Output is correct
6 Correct 246 ms 42568 KB Output is correct
7 Correct 321 ms 42620 KB Output is correct
8 Correct 302 ms 42488 KB Output is correct
9 Correct 324 ms 42776 KB Output is correct
10 Correct 252 ms 42488 KB Output is correct
11 Correct 319 ms 42608 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24064 KB Output is correct
2 Correct 2360 ms 161696 KB Output is correct
3 Correct 3406 ms 162672 KB Output is correct
4 Correct 906 ms 158980 KB Output is correct
5 Correct 4788 ms 182852 KB Output is correct
6 Correct 3471 ms 165144 KB Output is correct
7 Correct 901 ms 70068 KB Output is correct
8 Correct 411 ms 70244 KB Output is correct
9 Correct 1039 ms 74416 KB Output is correct
10 Correct 895 ms 71416 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24568 KB Output is correct
2 Correct 306 ms 42488 KB Output is correct
3 Correct 336 ms 42708 KB Output is correct
4 Correct 329 ms 42556 KB Output is correct
5 Correct 331 ms 42820 KB Output is correct
6 Correct 246 ms 42568 KB Output is correct
7 Correct 321 ms 42620 KB Output is correct
8 Correct 302 ms 42488 KB Output is correct
9 Correct 324 ms 42776 KB Output is correct
10 Correct 252 ms 42488 KB Output is correct
11 Correct 319 ms 42608 KB Output is correct
12 Correct 23 ms 24064 KB Output is correct
13 Correct 2360 ms 161696 KB Output is correct
14 Correct 3406 ms 162672 KB Output is correct
15 Correct 906 ms 158980 KB Output is correct
16 Correct 4788 ms 182852 KB Output is correct
17 Correct 3471 ms 165144 KB Output is correct
18 Correct 901 ms 70068 KB Output is correct
19 Correct 411 ms 70244 KB Output is correct
20 Correct 1039 ms 74416 KB Output is correct
21 Correct 895 ms 71416 KB Output is correct
22 Correct 2504 ms 169472 KB Output is correct
23 Correct 2458 ms 171692 KB Output is correct
24 Correct 3930 ms 172840 KB Output is correct
25 Correct 3947 ms 174992 KB Output is correct
26 Correct 3912 ms 172060 KB Output is correct
27 Correct 4729 ms 195528 KB Output is correct
28 Correct 1079 ms 169724 KB Output is correct
29 Correct 4353 ms 171140 KB Output is correct
30 Correct 4000 ms 172008 KB Output is correct
31 Correct 4103 ms 172016 KB Output is correct
32 Correct 1026 ms 75548 KB Output is correct
33 Correct 446 ms 70756 KB Output is correct
34 Correct 718 ms 67908 KB Output is correct
35 Correct 725 ms 67832 KB Output is correct
36 Correct 911 ms 68468 KB Output is correct
37 Correct 967 ms 68588 KB Output is correct