oj.uz

Submission #726362

# Submission time Handle Problem Language Result Execution time Memory
726362 2023-04-18T19:13:19 Z PoPularPlusPlus Factories (JOI14_factories) C++17
15 / 100
 8000 ms 199144 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13696 KB Output is correct
2 Correct 627 ms 32068 KB Output is correct
3 Correct 1869 ms 32360 KB Output is correct
4 Correct 805 ms 32336 KB Output is correct
5 Correct 694 ms 32424 KB Output is correct
6 Correct 465 ms 32204 KB Output is correct
7 Correct 1833 ms 32120 KB Output is correct
8 Correct 834 ms 32396 KB Output is correct
9 Correct 687 ms 32436 KB Output is correct
10 Correct 355 ms 32072 KB Output is correct
11 Correct 1936 ms 32104 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 13268 KB Output is correct
2 Correct 1725 ms 182544 KB Output is correct
3 Correct 6469 ms 184352 KB Output is correct
4 Correct 1402 ms 184060 KB Output is correct
5 Correct 4261 ms 199144 KB Output is correct
6 Correct 4612 ms 183732 KB Output is correct
7 Execution timed out 8036 ms 65216 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13696 KB Output is correct
2 Correct 627 ms 32068 KB Output is correct
3 Correct 1869 ms 32360 KB Output is correct
4 Correct 805 ms 32336 KB Output is correct
5 Correct 694 ms 32424 KB Output is correct
6 Correct 465 ms 32204 KB Output is correct
7 Correct 1833 ms 32120 KB Output is correct
8 Correct 834 ms 32396 KB Output is correct
9 Correct 687 ms 32436 KB Output is correct
10 Correct 355 ms 32072 KB Output is correct
11 Correct 1936 ms 32104 KB Output is correct
12 Correct 12 ms 13268 KB Output is correct
13 Correct 1725 ms 182544 KB Output is correct
14 Correct 6469 ms 184352 KB Output is correct
15 Correct 1402 ms 184060 KB Output is correct
16 Correct 4261 ms 199144 KB Output is correct
17 Correct 4612 ms 183732 KB Output is correct
18 Execution timed out 8036 ms 65216 KB Time limit exceeded
19 Halted 0 ms 0 KB -