oj.uz

Submission #934993

# Submission time Handle Problem Language Result Execution time Memory
934993 2024-02-28T10:08:13 Z Baizho Factories (JOI14_factories) C++14
100 / 100
 4933 ms 196908 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt")
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const long long inf = 5e18;
const long double eps = 1e-15L;
const int M = 5e5 + 10;


int n, m, par[M + 10], siz[M + 10], up[20][M + 10], col[M + 10], depth[M + 10], lc[M + 1][20];
bool del[M + 10];
long long dis[M + 10], wei[M + 10];
vector<pair<int, int> > g[M + 10];
 
void qfs(int v, int p = 0) {
	depth[v] = depth[p] + 1;
	dis[v] = inf;
	up[0][v] = p;
	for(int j = 1; j <= 19; j ++) up[j][v] = up[j - 1][up[j - 1][v]];
	for(auto to : g[v]) {
		if(to.ff == p) continue;
		wei[to.ff] = wei[v] + to.ss;
		qfs(to.ff, v);
	}
}
 
void dfs_size(int v, int p = -1) {
	siz[v] = 1;
	for(auto to : g[v]) {
		if(to.ff == p || del[to.ff]) continue;
		dfs_size(to.ff, v);
		siz[v] += siz[to.ff];
	}
}
 
int getc(int v, int n, int p = -1) {
//	cout<<v<<" yolo  "<<n<<endl;
	for(auto to : g[v]) {
		if(to.ff == p || del[to.ff] || siz[to.ff] <= n / 2) continue;
		return getc(to.ff, n, v);
	}
//	cout<<v<<endl;
	return v;
}
 
void decomp(int v, int p = 0) {
	dfs_size(v);
//	cout<<v<<" "<<p<<endl;
	int c = getc(v, siz[v]);
//	cout<<c<<" "<<endl;
	par[c] = p;
	del[c] = 1;
	for(auto to : g[c]) {
		if(del[to.ff]) continue;
		decomp(to.ff, c);
	}
}
 
int lca(int u, int v) {
	if(depth[u] < depth[v]) swap(u, v);
//	cout<<u<<" "<<v<<" "<<" "<<depth[u]<<" "<<depth[v]<<" ";
	int dif = depth[u] - depth[v];
	for(int j = 19; j >= 0; j --) {
		if(dif & (1 << j)) u = up[j][u];
	}
//	cout<<u<<" ";
	if(u == v) return u;
	for(int j = 19; j >= 0; j --) {
		if(up[j][u] != up[j][v]) {
			u  = up[j][u]; v = up[j][v];
		}
	}
//	cout<<up[0][u]<<"\n";
	return up[0][u];
}
 
long long dist(int u, int v, int up) {
//	cout<<u<<" "<<v<<" "<<depth[u] + depth[v] - depth[lca(u, v)] * 2<<"\n";
	return wei[u] + wei[v] - wei[lc[v][up]] * 2;
}
 
void add(long long v) {
	long long x = v, step = 0;
	while(v > 0) {
//		cout<<v<<" her1 "<<endl;
//		cout<<v<<" "<<dist(v, x)<<" "<<dis[v]<<" yolo \n"<<endl;
		dis[v] = min(dis[v], dist(v, x, step ++));
		v = par[v];
	}
}
 
void erase(long long v) {
	long long x = v;
	while(v > 0) {
//		cout<<v<<" her2 "<<endl;
//		cout<<v<<" "<<dist(v, x)<<" "<<dis[v]<<" yolo \n";
		dis[v] = inf;
		v = par[v];
	}
}
 
long long get(int v) {
	long long ans = inf, x = v, step = 0;
	while(v > 0) {
//		cout<<v<<" her3 "<<endl;
		ans = min(ans, dist(v, x, step ++) + dis[v]);
		v = par[v];
	}
	return ans;
}
 
void Init(int N, int A[], int B[], int D[]) {
//	cout<<N<<endl;
	n = N;
//	cout<<"YOLO "<<endl;
	for(int i = 0; i <= n - 2; i ++) {
		A[i] ++;
		B[i] ++;
		g[A[i]].pb({B[i], D[i]});
		g[B[i]].pb({A[i], D[i]});
	}
	qfs(1);
	decomp(1);
	for(int i = 1; i <= n; i ++) {
		int cur = i;
		for(int j = 0; j <= 19; j ++) {
			lc[i][j] = lca(i, cur);
			cur = par[cur];
		}
	}
//	cout<<"\n";
}
 
long long Query(int S, int X[], int T, int Y[]) {
	for(int i = 0; i < S; i ++) {
		X[i] ++;
		add(X[i]);
	}
	long long ans = inf;
	for(int i = 0; i < T; i ++) {
		Y[i] ++;
		ans = min(ans, get(Y[i]));
	}
//	cout<<"YOLO "<<endl;
	for(int i = 0; i < S; i ++) {
		erase(X[i]);
	}
	return ans;
}

Compilation message

factories.cpp: In function 'void erase(long long int)':
factories.cpp:114:12: warning: unused variable 'x' [-Wunused-variable]
  114 |  long long x = v;
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 76380 KB Output is correct
2 Correct 215 ms 81296 KB Output is correct
3 Correct 236 ms 81292 KB Output is correct
4 Correct 226 ms 81236 KB Output is correct
5 Correct 241 ms 81564 KB Output is correct
6 Correct 150 ms 81232 KB Output is correct
7 Correct 228 ms 81288 KB Output is correct
8 Correct 233 ms 81292 KB Output is correct
9 Correct 240 ms 81492 KB Output is correct
10 Correct 152 ms 81232 KB Output is correct
11 Correct 228 ms 81300 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 76380 KB Output is correct
2 Correct 1572 ms 146480 KB Output is correct
3 Correct 3349 ms 152324 KB Output is correct
4 Correct 689 ms 147380 KB Output is correct
5 Correct 4249 ms 179708 KB Output is correct
6 Correct 3409 ms 152680 KB Output is correct
7 Correct 628 ms 96848 KB Output is correct
8 Correct 283 ms 96744 KB Output is correct
9 Correct 679 ms 100232 KB Output is correct
10 Correct 644 ms 97360 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 76380 KB Output is correct
2 Correct 215 ms 81296 KB Output is correct
3 Correct 236 ms 81292 KB Output is correct
4 Correct 226 ms 81236 KB Output is correct
5 Correct 241 ms 81564 KB Output is correct
6 Correct 150 ms 81232 KB Output is correct
7 Correct 228 ms 81288 KB Output is correct
8 Correct 233 ms 81292 KB Output is correct
9 Correct 240 ms 81492 KB Output is correct
10 Correct 152 ms 81232 KB Output is correct
11 Correct 228 ms 81300 KB Output is correct
12 Correct 12 ms 76380 KB Output is correct
13 Correct 1572 ms 146480 KB Output is correct
14 Correct 3349 ms 152324 KB Output is correct
15 Correct 689 ms 147380 KB Output is correct
16 Correct 4249 ms 179708 KB Output is correct
17 Correct 3409 ms 152680 KB Output is correct
18 Correct 628 ms 96848 KB Output is correct
19 Correct 283 ms 96744 KB Output is correct
20 Correct 679 ms 100232 KB Output is correct
21 Correct 644 ms 97360 KB Output is correct
22 Correct 1945 ms 147824 KB Output is correct
23 Correct 1998 ms 148828 KB Output is correct
24 Correct 3878 ms 150432 KB Output is correct
25 Correct 3888 ms 175380 KB Output is correct
26 Correct 3814 ms 173620 KB Output is correct
27 Correct 4933 ms 196908 KB Output is correct
28 Correct 853 ms 172208 KB Output is correct
29 Correct 3882 ms 175020 KB Output is correct
30 Correct 3799 ms 174336 KB Output is correct
31 Correct 3837 ms 174900 KB Output is correct
32 Correct 720 ms 115096 KB Output is correct
33 Correct 271 ms 110588 KB Output is correct
34 Correct 487 ms 109316 KB Output is correct
35 Correct 472 ms 109188 KB Output is correct
36 Correct 670 ms 110160 KB Output is correct
37 Correct 647 ms 109940 KB Output is correct