Submission #726362

#	Time	Username	Problem	Language	Result	Execution time	Memory
726362		PoPularPlusPlus	Factories (JOI14_factories)	C++17	15 / 100	8036 ms	199144 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std; 

#define ll long long
#define pb(e) push_back(e)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second

const int N = 500002,L=20;
int n;
vector<pair<int,int>> adj[N];
int tin[N],tout[N],timer,up[N][L];
ll dis[N][L];
bool there[N],there1[N];
ll diss[N],diss1[N] , best[N],best1[N];

void dfs(int node , int par , int di){
	tin[node] = timer++;
	up[node][0] = par;
	dis[node][0] = di;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
		dis[node][i] = dis[node][i-1] + dis[up[node][i-1]][i-1];
	}
	for(auto i : adj[node]){
		if(i.vf != par){
			dfs(i.vf , node , i.vs);
		}
	}
	tout[node] = timer++;
}

bool is_lca(int x , int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int find(int x , int y){
	if(is_lca(x,y))return x;
	if(is_lca(y,x))return y;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i] , y))x = up[x][i];
	}
	return up[x][0];
}

void Init(int nn, int A[], int B[], int D[]) {
	n = nn;
	for(int i = 0; i < n-1; i++){
		adj[A[i]].pb(mp(B[i],D[i]));
		adj[B[i]].pb(mp(A[i],D[i]));
	}
	memset(there,0,sizeof there);
	memset(there1,0,sizeof there1);
	timer = 0;
	dfs(0,0,0);
}

ll cal(int x , int y){
	if(x == y)return 0;
	ll ans = 0;
	for(int i = L - 1; i >= 0; i--){
		if(!is_lca(up[x][i] , y)){
			ans += dis[x][i];
			x = up[x][i];
		}
	}
	ans += dis[x][0];
	return ans;
}

ll brute(int a , int x[] , int b , int y[]){
	ll ans = 1e18;
	for(int i = 0; i < a; i++){
		for(int j = 0; j < b; j++){
			int lca = find(x[i] , y[j]);
			//cout << x[i] << ' ' << y[j] << ' ' << lca << ' ' << cal(x[i] , lca) << ' ' << cal(y[i] , lca) << '\n';
			ans = min(ans , cal(x[i] , lca) + cal(y[j] , lca));
		}
	}
	return ans;
}

void dfs1(int node , int par){
	best[node] = best1[node] = diss[node] = diss1[node] = 1e18;
	if(there[node])best[node] = diss[node] = 0;
	if(there1[node])best1[node] = diss1[node] = 0;
	if(there[node] && there1[node]){
		cout << "came " << node << '\n';
	}
	for(auto i : adj[node]){
		if(i.vf != par){
			dfs1(i.vf , node);
			ll di = best[i.vf] + i.vs;
			if(best[node] > di){
				diss[node] = best[node];
				best[node] = di;
			}
			else {
				diss[node] = min(diss[node] , di);
			}
			di = best1[i.vf] + i.vs;
			if(best1[node] > di){
				diss1[node] = best1[node];
				best1[node] = di;
			}
			else diss1[node] = min(diss1[node] , di);
		}
	}
}

void dfs2(int node , int par , ll di , ll di1){
	best[node] = min(best[node] , di);
	best1[node] = min(best1[node] , di1);
	diss[node] = min(diss[node], di);
	diss1[node] = min(diss1[node] , di1);
	for(auto i : adj[node]){
		if(i.vf != par){
			ll d = i.vs;
			ll d1 = i.vs;
			if(best[node] == best[i.vf] + i.vs)d += diss[node];
			else d += best[node];
			if(best1[node] == best1[i.vf] + i.vs)d1 += diss1[node];
			else d1 += best1[node];
			dfs2(i.vf , node , d, d1);
		}
	}
}

ll full(int a , int x[] , int b , int y[]){
	for(int i = 0; i < a; i++)there[x[i]] = 1;
	for(int i = 0; i < b; i++)there1[y[i]] = 1;
	dfs1(0 , 0);
	dfs2(0,0,1e18,1e18);
	ll res = 1e18;
	for(int i = 0; i < n; i++){
		res = min(res , best[i] + best1[i]);
		//cout << best[i] << ' ' << best1[i] << '\n';
	}
	for(int i = 0; i < a; i++)there[x[i]] = 0;
	for(int i = 0; i < b; i++)there1[y[i]] = 0;
	return res;
}

long long Query(int a, int x[], int b, int y[]) {
	if(a*b <= n)return brute(a,x,b,y);
	return full(a,x,b,y);
}

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