oj.uz

Submission #519219

# Submission time Handle Problem Language Result Execution time Memory
519219 2022-01-26T03:25:36 Z amunduzbaev Factories (JOI14_factories) C++14
100 / 100
 2664 ms 161304 KB 
#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#include "factories.h"
#define ar array

const int M = 5e5 + 5;
vector<ar<int, 2>> edges[M];
int tin[M], tout[M], t, par[M][20];
long long d[M]; 

void dfs(int u, int p = -1){
	tin[u] = ++t;
	for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
	for(auto x : edges[u]){
		if(x[0] == p) continue;
		d[x[0]] = d[u] + x[1];
		par[x[0]][0] = u;
		dfs(x[0], u);
	} tout[u] = t;
}

int is[M];

bool iis(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int lca(int a, int b){
	if(iis(a, b)) return a;
	if(iis(b, a)) return b;
	//~ cout<<tin[1]<<" "<<tout[1]<<" "<<tin[6]<<" "<<tout[6]<<"\n";
	for(int i=19;~i;i--){
		if(!iis(par[a][i], b)) a = par[a][i];
	} // cout<<a<<"\n";
	return par[a][0];
}

vector<int> tmp;
vector<ar<long long, 2>> ee[M];
long long dp[M], up[M];

void go(int u, int p = -1){
	if(is[tmp[u]] == 1) dp[u] = 0;
	for(auto x : ee[u]){
		if(x[0] == p) continue;
		go(x[0], u);
		dp[u] = min(dp[u], dp[x[0]] + x[1]);
	} // cout<<u<<" "<<dp[u]<<"\n";
}

void re(int u, int p = -1){
	if(p == -1) up[u] = 1e18;
	dp[u] = min(dp[u], up[u]);
	if(is[tmp[u]] == 1) up[u] = 0;
	for(auto x : ee[u]){
		if(x[0] == p) continue;
		up[x[0]] = up[u];
		up[u] = min(up[u], dp[x[0]] + x[1]);
	}
	
	reverse(ee[u].begin(), ee[u].end());
	up[u] = 1e18;
	for(auto x : ee[u]){
		if(x[0] == p) continue;
		up[x[0]] = min(up[x[0]], up[u]);
		up[u] = min(up[u], dp[x[0]] + x[1]);
		up[x[0]] += x[1];
		re(x[0], u);
	}
}

void Init(int n, int a[], int b[], int d[]) {
	for(int i=0;i+1<n;i++){
		edges[a[i]].push_back({b[i], d[i]});
		edges[b[i]].push_back({a[i], d[i]});
	}
	
	dfs(0);
}

long long Query(int s, int x[], int t, int y[]) {
	if(s < t) swap(s, t), swap(x, y);
	for(int i=0;i<s;i++){
		is[x[i]] = 1;
	}
	
	long long res = 1e18;
	for(int i=0;i<t;i++){
		if(is[y[i]] == 1) res = 0;
		is[y[i]] = 2;
	}
	
	if(!res){
		for(int i=0;i<s;i++) is[x[i]] = 0;
		for(int i=0;i<t;i++) is[y[i]] = 0;
		return res;
	}
	
	tmp.clear();
	for(int i=0;i<s;i++) tmp.push_back(x[i]);
	for(int i=0;i<t;i++) tmp.push_back(y[i]);
	sort(tmp.begin(), tmp.end(), [&](int i, int j) { return (tin[i] < tin[j]); });
	int m = (int)tmp.size();
	for(int i=1;i<m;i++){
		tmp.push_back(lca(tmp[i-1], tmp[i]));
		//~ cout<<tmp[i-1]<<" "<<tmp[i]<<" "<<lca(tmp[i-1], tmp[i])<<"\n";
	}
	
	sort(tmp.begin(), tmp.end(), [&](int i, int j) { 
		if(tin[i] != tin[j]) return (tin[i] < tin[j]); 
		return tout[i] > tout[j];
	});
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	
	//~ for(auto x : tmp) cout<<x<<" ";
	//~ cout<<"\n";
	
	m = (int)tmp.size();
	vector<int> nxt(m);
	for(int i=0;i<m;i++){
		int l = i + 1, r = m;
		while(l < r){
			int m = (l + r) >> 1;
			if(tin[tmp[m]] <= tout[tmp[i]]) l = m + 1;
			else r = m;
		}
		
		nxt[i] = l;
		ee[i].clear();
		dp[i] = 1e18;
	}
	
	//~ for(int i=0;i<m;i++) cout<<nxt[i]<<" ";
	//~ cout<<"\n";
	
	for(int i=0;i<m;i++){
		int j = i + 1;
		while(j < nxt[i]){
			ee[i].push_back({j, d[tmp[j]] - d[tmp[i]]});
			j = nxt[j];
		}
	}
	
	go(0);
	re(0);
	for(int i=0;i<m;i++){
		if(is[tmp[i]] == 2) res = min(res, dp[i]);
	}
	for(int i=0;i<m;i++) is[tmp[i]] = 0;
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24220 KB Output is correct
2 Correct 938 ms 42692 KB Output is correct
3 Correct 909 ms 42232 KB Output is correct
4 Correct 944 ms 42688 KB Output is correct
5 Correct 683 ms 42488 KB Output is correct
6 Correct 708 ms 42236 KB Output is correct
7 Correct 888 ms 42196 KB Output is correct
8 Correct 911 ms 42736 KB Output is correct
9 Correct 682 ms 42448 KB Output is correct
10 Correct 664 ms 42356 KB Output is correct
11 Correct 893 ms 42244 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24012 KB Output is correct
2 Correct 1221 ms 122928 KB Output is correct
3 Correct 1624 ms 124480 KB Output is correct
4 Correct 893 ms 123204 KB Output is correct
5 Correct 1064 ms 153688 KB Output is correct
6 Correct 1738 ms 126692 KB Output is correct
7 Correct 1368 ms 62188 KB Output is correct
8 Correct 792 ms 63032 KB Output is correct
9 Correct 657 ms 66584 KB Output is correct
10 Correct 1312 ms 63668 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 24220 KB Output is correct
2 Correct 938 ms 42692 KB Output is correct
3 Correct 909 ms 42232 KB Output is correct
4 Correct 944 ms 42688 KB Output is correct
5 Correct 683 ms 42488 KB Output is correct
6 Correct 708 ms 42236 KB Output is correct
7 Correct 888 ms 42196 KB Output is correct
8 Correct 911 ms 42736 KB Output is correct
9 Correct 682 ms 42448 KB Output is correct
10 Correct 664 ms 42356 KB Output is correct
11 Correct 893 ms 42244 KB Output is correct
12 Correct 17 ms 24012 KB Output is correct
13 Correct 1221 ms 122928 KB Output is correct
14 Correct 1624 ms 124480 KB Output is correct
15 Correct 893 ms 123204 KB Output is correct
16 Correct 1064 ms 153688 KB Output is correct
17 Correct 1738 ms 126692 KB Output is correct
18 Correct 1368 ms 62188 KB Output is correct
19 Correct 792 ms 63032 KB Output is correct
20 Correct 657 ms 66584 KB Output is correct
21 Correct 1312 ms 63668 KB Output is correct
22 Correct 2405 ms 145316 KB Output is correct
23 Correct 2117 ms 145748 KB Output is correct
24 Correct 2435 ms 144116 KB Output is correct
25 Correct 2523 ms 147808 KB Output is correct
26 Correct 2626 ms 133264 KB Output is correct
27 Correct 1880 ms 161304 KB Output is correct
28 Correct 1468 ms 141704 KB Output is correct
29 Correct 2622 ms 132528 KB Output is correct
30 Correct 2582 ms 132076 KB Output is correct
31 Correct 2664 ms 132964 KB Output is correct
32 Correct 1091 ms 72988 KB Output is correct
33 Correct 960 ms 68420 KB Output is correct
34 Correct 1372 ms 60932 KB Output is correct
35 Correct 1271 ms 60800 KB Output is correct
36 Correct 1440 ms 60876 KB Output is correct
37 Correct 1439 ms 60872 KB Output is correct