oj.uz

Submission #394131

# Submission time Handle Problem Language Result Execution time Memory
394131 2021-04-25T17:55:35 Z SavicS Factories (JOI14_factories) C++14
100 / 100
 6856 ms 173528 KB 
#include "factories.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 500005;
const ll inf = 1e18 + 5;
 
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)
 
int n, q;
 
vector<pii> g[maxn];
 
int par[maxn];
 
int cnt[maxn];
bool bio[maxn];
void dfs_size(int v, int p) {
	cnt[v] = 1;
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		dfs_size(u, v);
		cnt[v] += cnt[u];
	}
}
 
int centroid(int v, int p, int vel) {
	for(auto c : g[v]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		if(cnt[u] > vel / 2)return centroid(u, v, vel);
	}
	return v;
}
 
void decompose(int v, int p) {
	dfs_size(v, p);
 
	int cen = centroid(v, p, cnt[v]);
	bio[cen] = 1;
 
	par[cen] = p;
	for(auto c : g[cen]) {
		int u = c.fi;
		int w = c.se;
		if(u == p || bio[u])continue;
		decompose(u, cen);
	}
 
}
 
vector<int> euler;

int d[maxn];
int in[maxn];
ll dist[maxn];
void dfs(int v, int p){
	in[v] = sz(euler);
	euler.pb(v);
	for(auto c : g[v]){
		int u = c.fi;
		int w = c.se;
		if(u != p){
			d[u] = d[v] + 1;
			dist[u] = dist[v] + w;
			dfs(u, v);
			euler.pb(v);	
		}
	}
}

int cmb(int X, int Y){
	return (d[X] > d[Y] ? Y : X);
}

int sp[10 * maxn][20];
void init_sp(){
	int N = sz(euler);
	ff(i,0,N - 1)sp[i][0] = euler[i];
	ff(j,1,19){
		for(int i = 0;i + (1 << j) - 1 < N; i++){
			sp[i][j] = cmb(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int rmq(int l, int r){
	int x = 31 - __builtin_clz(r - l + 1);
	return cmb(sp[l][x], sp[r - (1 << x) + 1][x]);
}

int lca(int x, int y){
	x = in[x], y = in[y];
	if(x > y)swap(x, y);
	return rmq(x, y);
}
 
// treba mi lca u O(1)
ll distance(int x, int y) {
	return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}
 
 
ll best[maxn];
void upd(int X, int Y) {
	for(int A = X ; A != 0 ; A = par[A]) {
		
		if(Y == 1)best[A] = min(best[A], distance(A, X));
		else best[A] = inf;
		 
	}
}
 
ll kve(int X) {
	ll ans = inf;
	for(int A = X ; A != 0 ; A = par[A]) {
		ans = min(ans, best[A] + distance(A, X));
	}
	return ans;
}
 
void Init(int N, int A[], int B[], int D[]) {
	n = N;
	ff(i,0,n - 2) {
		int u = A[i] + 1;
		int v = B[i] + 1;
		int w = D[i];
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
 
	decompose(1, 0);
	dfs(1, 0);
	init_sp();
 
	ff(i,1,n)best[i] = inf;
}
 
ll Query(int S, int X[], int T, int Y[]) {
	ff(i,0,S - 1) {
		int A = X[i] + 1;
		upd(A, 1);
	}
 
	ll ans = inf;
	ff(i,0,T - 1) {
		int B = Y[i] + 1;
		ans = min(ans, kve(B));
	}
	
	ff(i,0,S - 1){
		int A = X[i] + 1;
		upd(A, -1);
	}
	
	return ans;
 
}
 
//int main()
//{
//    ios::sync_with_stdio(false);
//    cout.tie(nullptr);
//    cin.tie(nullptr);
//	cin >> n >> q;
//	ff(i,1,n - 1){
//		int u, v, w;
//		cin >> u >> v >> w;
//		u++, v++;
//		g[u].pb({v, w});
//		g[v].pb({u, w});
//	}
//
//	decompose(1, 0);
//	dfs(1, 0);
//	init_sp();
//
//	ff(i,1,n)best[i] = inf;
//
//	while(q--){
//		int S, T;
//		cin >> S >> T;
//
//		ff(i,1,S){
//			int X;
//			cin >> X;
//			X++;
//			upd(X, 1);
//		}
//
//		ll ans = inf;
//		ff(i,1,T){
//			int X;
//			cin >> X;
//			X++;
//			ans = min(ans, kve(X));
//		}
//		cout << ans << endl;
//		
//	}
//
//    return 0;
//}
/**

7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4


// probati bojenje sahovski ili slicno

**/

Compilation message

factories.cpp: In function 'void dfs_size(int, int)':
factories.cpp:41:7: warning: unused variable 'w' [-Wunused-variable]
   41 |   int w = c.se;
      |       ^
factories.cpp: In function 'int centroid(int, int, int)':
factories.cpp:51:7: warning: unused variable 'w' [-Wunused-variable]
   51 |   int w = c.se;
      |       ^
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:67:7: warning: unused variable 'w' [-Wunused-variable]
   67 |   int w = c.se;
      |       ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12580 KB Output is correct
2 Correct 512 ms 30796 KB Output is correct
3 Correct 655 ms 30812 KB Output is correct
4 Correct 640 ms 30800 KB Output is correct
5 Correct 693 ms 31200 KB Output is correct
6 Correct 350 ms 30756 KB Output is correct
7 Correct 639 ms 30832 KB Output is correct
8 Correct 688 ms 30876 KB Output is correct
9 Correct 681 ms 31044 KB Output is correct
10 Correct 335 ms 30820 KB Output is correct
11 Correct 641 ms 30852 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12364 KB Output is correct
2 Correct 2861 ms 160664 KB Output is correct
3 Correct 3821 ms 145052 KB Output is correct
4 Correct 1282 ms 143420 KB Output is correct
5 Correct 5211 ms 173528 KB Output is correct
6 Correct 3922 ms 146440 KB Output is correct
7 Correct 2012 ms 60660 KB Output is correct
8 Correct 719 ms 61116 KB Output is correct
9 Correct 2171 ms 64976 KB Output is correct
10 Correct 1996 ms 61916 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12580 KB Output is correct
2 Correct 512 ms 30796 KB Output is correct
3 Correct 655 ms 30812 KB Output is correct
4 Correct 640 ms 30800 KB Output is correct
5 Correct 693 ms 31200 KB Output is correct
6 Correct 350 ms 30756 KB Output is correct
7 Correct 639 ms 30832 KB Output is correct
8 Correct 688 ms 30876 KB Output is correct
9 Correct 681 ms 31044 KB Output is correct
10 Correct 335 ms 30820 KB Output is correct
11 Correct 641 ms 30852 KB Output is correct
12 Correct 9 ms 12364 KB Output is correct
13 Correct 2861 ms 160664 KB Output is correct
14 Correct 3821 ms 145052 KB Output is correct
15 Correct 1282 ms 143420 KB Output is correct
16 Correct 5211 ms 173528 KB Output is correct
17 Correct 3922 ms 146440 KB Output is correct
18 Correct 2012 ms 60660 KB Output is correct
19 Correct 719 ms 61116 KB Output is correct
20 Correct 2171 ms 64976 KB Output is correct
21 Correct 1996 ms 61916 KB Output is correct
22 Correct 3833 ms 144248 KB Output is correct
23 Correct 3913 ms 146588 KB Output is correct
24 Correct 5341 ms 146840 KB Output is correct
25 Correct 5425 ms 150416 KB Output is correct
26 Correct 5485 ms 147220 KB Output is correct
27 Correct 6856 ms 170160 KB Output is correct
28 Correct 1616 ms 147332 KB Output is correct
29 Correct 5393 ms 146840 KB Output is correct
30 Correct 5426 ms 145968 KB Output is correct
31 Correct 5430 ms 146872 KB Output is correct
32 Correct 2243 ms 66124 KB Output is correct
33 Correct 728 ms 61532 KB Output is correct
34 Correct 1584 ms 58296 KB Output is correct
35 Correct 1602 ms 58424 KB Output is correct
36 Correct 2048 ms 58880 KB Output is correct
37 Correct 2005 ms 59092 KB Output is correct