oj.uz

Submission #1086806

# Submission time Handle Problem Language Result Execution time Memory
1086806 2024-09-11T13:56:49 Z Sunbae Factories (JOI14_factories) C++17
100 / 100
 7268 ms 224056 KB 
#include "factories.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define z exit(0)
#define F first
#define S second
#define mp make_pair
typedef long long ll;
using namespace std;
using pii = pair<int,int>;
const int N = 5e5 + 5, M = 1e6 + 5;
const ll inf = 1e18;
vector<pii> g[N]; vector<int> vt_g[N];
int col[N], tin[N], tout[N], LOG, m, euler[M], ST[M][21], T[M], V[N], st[N], vis[N];
ll dp[N];
 
void dfs(int u, int p){
	euler[m++] = u;
	for(pii it: g[u]){
		int w = it.F, v = it.S;
		if(v != p){ dp[v] = dp[u] + w; dfs(v, u); euler[m++] = u;}
	}
}
int LCA(int u, int v){
	int l = tin[u], r =  tin[v]; 
	if(l > r) swap(l, r);
	int j = 31 - __builtin_clz(r-l+1);
	return T[min(ST[l][j], ST[r-(1<<j)+1][j])];
}
 
ll d(int u, int v){ return dp[u] + dp[v] - (dp[LCA(u, v)]<<1LL);}
 
void Init(int n, int A[], int B[], int D[]){
	for(int i = 0; i<n; ++i){ g[i].clear(); } 
	for(int i = 0, u, v, w; i<n-1; ++i){
		u = A[i]; v = B[i]; w = D[i];
		g[u].emplace_back(w, v); g[v].emplace_back(w, u);
	}
	dp[0] = m = 0; dfs(0, 0); LOG = 32 - __builtin_clz(m); 
	for(int i = m-1; i>=0; --i) tin[euler[i]] = tout[euler[i]] = i, T[i] = euler[i];
	for(int i = 0; i<m; ++i) tout[euler[i]] = i, ST[i][0] = tin[euler[i]];
	for(int j = 1; j<LOG; ++j){
		for(int i = 0; i+(1<<j)-1<m; ++i){
			ST[i][j] = min(ST[i][j-1], ST[i+(1<<(j-1))][j-1]);
		}
	}
}
bool anc(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u];}
int ded[N], sz[N], ct; ll ans, mn[3];
int fsz(int u, int p){ sz[u] = 1; for(int v: vt_g[u]) if(!ded[v] && v != p) sz[u] += fsz(v, u); return sz[u];}
int fcen(int u, int p, int tsz){ for(int v: vt_g[u]) if(!ded[v] && sz[v] > tsz/2 && v != p) return fcen(v, u, tsz); return u;}
 
void efs(int u, int p){
	if(col[u] && col[ct] && col[u] != col[ct]) ans = min(ans, d(ct, u));
	if(col[u] == 1 && mn[2] < inf) ans = min(ans, d(ct, u) + mn[2]);
	if(col[u] == 2 && mn[1] < inf) ans = min(ans, d(ct, u) + mn[1]);
	for(int v: vt_g[u]) if(!ded[v] && v != p) efs(v, u);
}
 
void ffs(int u, int p){
	mn[col[u]] = min(mn[col[u]], d(ct, u));
	for(int v: vt_g[u]) if(!ded[v] && v != p) ffs(v, u);
}	
void cd(int u){
	ded[ct = u = fcen(u, -1, fsz(u, -1))] = true;
	for(int v: vt_g[u]) if(!ded[v]) efs(v, u), ffs(v, u);
	mn[0] = mn[1] = mn[2] = inf;
	for(int v: vt_g[u]) if(!ded[v]) cd(v);
}
ll Query(int s, int X[], int t, int Y[]){
	bool ch = false;
	for(int i = m = 0; i<s; ++i){ col[X[i]] = 1; vis[X[i]] = 1; V[m++] = X[i];}
	for(int i = 0; i<t; ++i){ col[Y[i]] = 2; V[m++] = Y[i]; if(vis[Y[i]]) ch = true;}
	auto cmp = [&](int u, int v) { return tin[u] < tin[v];}; 
	sort(V, V+m, cmp);
	int mm = m;
	for(int i = 1; i<m; ++i) V[mm++] = LCA(V[i-1], V[i]);
	m = mm; sort(V, V+m); m = unique(V, V+m) - V; sort(V, V+m, cmp);	
	//
	int sz = 0;
	st[sz++] = V[0];
	for(int i = 1; i<m; ++i){
		for(; sz > 1 && !anc(st[sz-1], V[i]); --sz) vt_g[st[sz-2]].push_back(st[sz-1]), vt_g[st[sz-1]].push_back(st[sz-2]);
		st[sz++] = V[i];
		
	}
	for(; sz > 1; --sz) vt_g[st[sz-2]].push_back(st[sz-1]), vt_g[st[sz-1]].push_back(st[sz-2]);
	ans = mn[0] = mn[1] = mn[2] = inf; cd(V[0]);
	for(int i = 0; i<m; ++i) col[V[i]] = ded[V[i]] = vis[V[i]] = 0, vt_g[V[i]].clear();
	if(ch) ans = 0;
	return ans;
}
/*
signed main(){
	int n, q; scanf("%d %d", &n, &q);
	int A[n], B[n], D[n], X[n], Y[n];
	for(int i = 0, u, v, w; i<n-1; ++i){
		scanf("%d %d %d", &u, &v, &w); 
		A[i] = u; B[i] = v; D[i] = w;
	}
	Init(n, A, B, D); 
	for(int i = 0; i<q; ++i){
		int s, t; scanf("%d %d", &s, &t);
		for(int j = 0; j<s; ++j) scanf("%d", X+j);
		for(int j = 0; j<t; ++j) scanf("%d", Y+j); 
		printf("%lld\n", Query(s, X, t, Y));
	}
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24408 KB Output is correct
2 Correct 1297 ms 42868 KB Output is correct
3 Correct 1725 ms 42828 KB Output is correct
4 Correct 1608 ms 42880 KB Output is correct
5 Correct 1313 ms 43092 KB Output is correct
6 Correct 549 ms 42832 KB Output is correct
7 Correct 1757 ms 42856 KB Output is correct
8 Correct 1599 ms 42832 KB Output is correct
9 Correct 1326 ms 43092 KB Output is correct
10 Correct 546 ms 42832 KB Output is correct
11 Correct 1698 ms 42832 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24152 KB Output is correct
2 Correct 1169 ms 193692 KB Output is correct
3 Correct 1373 ms 193916 KB Output is correct
4 Correct 799 ms 193972 KB Output is correct
5 Correct 1039 ms 217716 KB Output is correct
6 Correct 1327 ms 196436 KB Output is correct
7 Correct 1567 ms 76628 KB Output is correct
8 Correct 573 ms 77512 KB Output is correct
9 Correct 831 ms 80208 KB Output is correct
10 Correct 1343 ms 78164 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24408 KB Output is correct
2 Correct 1297 ms 42868 KB Output is correct
3 Correct 1725 ms 42828 KB Output is correct
4 Correct 1608 ms 42880 KB Output is correct
5 Correct 1313 ms 43092 KB Output is correct
6 Correct 549 ms 42832 KB Output is correct
7 Correct 1757 ms 42856 KB Output is correct
8 Correct 1599 ms 42832 KB Output is correct
9 Correct 1326 ms 43092 KB Output is correct
10 Correct 546 ms 42832 KB Output is correct
11 Correct 1698 ms 42832 KB Output is correct
12 Correct 13 ms 24152 KB Output is correct
13 Correct 1169 ms 193692 KB Output is correct
14 Correct 1373 ms 193916 KB Output is correct
15 Correct 799 ms 193972 KB Output is correct
16 Correct 1039 ms 217716 KB Output is correct
17 Correct 1327 ms 196436 KB Output is correct
18 Correct 1567 ms 76628 KB Output is correct
19 Correct 573 ms 77512 KB Output is correct
20 Correct 831 ms 80208 KB Output is correct
21 Correct 1343 ms 78164 KB Output is correct
22 Correct 4513 ms 203052 KB Output is correct
23 Correct 3311 ms 205724 KB Output is correct
24 Correct 7268 ms 204700 KB Output is correct
25 Correct 6064 ms 208436 KB Output is correct
26 Correct 5561 ms 203952 KB Output is correct
27 Correct 4783 ms 224056 KB Output is correct
28 Correct 1525 ms 206808 KB Output is correct
29 Correct 4534 ms 203672 KB Output is correct
30 Correct 4558 ms 203088 KB Output is correct
31 Correct 4446 ms 203604 KB Output is correct
32 Correct 2504 ms 82156 KB Output is correct
33 Correct 805 ms 79048 KB Output is correct
34 Correct 2267 ms 74580 KB Output is correct
35 Correct 2251 ms 74632 KB Output is correct
36 Correct 3427 ms 74836 KB Output is correct
37 Correct 3301 ms 75092 KB Output is correct