oj.uz

Submission #371998

# Submission time Handle Problem Language Result Execution time Memory
371998 2021-02-27T07:39:22 Z RohamIzadidoost Factories (JOI14_factories) C++14
100 / 100
 6383 ms 166752 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 5000*100+5 ;
const ll inf = 9223372036775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 19 ;
ll dis[maxn] , d[maxn] , ans , mark[maxn]; int L , R , h[maxn] , par[lg][maxn] , n , st[maxn] , ft[maxn]  , cnt , q[maxn] , Q ; 
vec<pll> adj[maxn] , g[maxn];
vec<int> t ;
stack<int> s ; 
bool cmp(const int &i ,const int &j){
	return (st[i] < st[j]) ; 
}
void predfs(int v , int p){
	st[v] = cnt ; cnt++ ; 
	for(auto u : adj[v]){
		if(u.X != p){
			h[u.X] = h[v] + 1 ; 
			dis[u.X] = dis[v] + u.Y ;
			par[0][u.X] = v ; 
			for(int i = 1 ;i <lg ; i ++ ) par[i][u.X] = par[i-1][par[i-1][u.X]] ;
			predfs(u.X , v) ;  
		}
	}
	ft[v] = cnt ; 
}
int lca(int u , int v){
	if(h[u] > h[v]) swap(u , v) ;
	/*for(int i = lg- 1 ; i >= 0 ; i -- ){
		if(par[i][v] != -1 && h[par[i][v]] >= h[u]) v = par[i][v] ; 
	}*/
	for(int i = h[v] - h[u] ; i ; i -= i & -i){
		v = par[__builtin_ctz(i)][v] ; 
	}
	if(v==u) return v ; 
	for(int i = lg - 1 ; i>= 0 ; i -- ){
		if(par[i][v] != par[i][u]){
			v = par[i][v] ; 
			u = par[i][u] ; 
		}
	}
	return par[0][u] ; 
}
/*
int main(){
	cin>>n>>Q ; 
	for(int i = 1 ; i < n ; i ++ ){
		ll u , v , w ; 
		cin>>u>>v>>w ; 
		adj[u].pb({v , w}) ; 
		adj[v].pb({u , w}) ; 
	}
	for(int i = 0 ;i < lg ; i ++ ) par[i][0] = -1 ;  
	predfs(0 , -1) ; 
	while(Q--){
		int S , T ; 
		cin>>S>>T ; 
		int X[S] , Y[T] ; 
		for(int i = 0 ; i < S ; i ++ ) cin>>X[i] ; 
		for(int i = 0 ; i < T ; i ++ ) cin>>Y[i] ; 
		//////////////////////////////////////////
L = R= 0 ; 
	for(int i = 0 ; i < S ; i ++ ){
		t.pb(X[i]) ; 
		q[R++] = X[i] ; 
	}
	for(int i = 0 ; i <T ; i ++ ){
		t.pb(Y[i]) ; mark[Y[i]] = 1 ; 
	}
	sort(all(t) , cmp) ; 
	for(int i = 0 ; i < T + S - 1 ; i ++ ){
		t.pb(lca(t[i] , t[i + 1])) ; 
	}t.pb(lca(t[T+S-1] , t[0])) ; 
	sort(all(t) , cmp) ; t.resize(unique(all(t)) - t.begin()) ; 
	for(auto u : t){
		d[u] = inf ; 
		while(s.size() && !( st[s.top()] < st[u] && ft[u] <= ft[s.top()] ) ) s.pop() ; 
		if(s.size()){
			g[u].pb({s.top() , dis[u] - dis[s.top()] }) ; 
			g[s.top()].pb({u , dis[u] - dis[s.top()] }) ; 
		}
		s.push(u) ; 
	}
	for(int i = 0 ; i < S ; i ++ ) d[X[i]] = 0 ; 
	ans = inf ; 
	while(L < R){
		int v = q[L++] ; 
		for(auto u : g[v]){
			if(d[u.X] > d[v] + u.Y){
				d[u.X] = d[v] + u.Y ; 
				q[R++] = u.X ; 
				if(mark[u.X])ans = min(ans , d[u.X]) ; 
			}
		}
	}
	for(auto u : t){
		g[u].clear() ; 
	}
	for(int i = 0 ; i < T ; i ++ ) mark[Y[i]] = 0 ; 
	t.clear() ; while(SZ(s)) s.pop() ; 
		cout<<ans << endl ; 
		/////////////////// 
	}
}*/
void Init(int N ,int A[] , int B[] , int D[])
{
	migmig ;
	for(int i = 0 ; i < N-1 ; i ++ ){
		adj[A[i]].pb({B[i] , D[i]}) ; 
		adj[B[i]].pb({A[i] , D[i]}) ; 
	}
	for(int i = 0 ;i < lg ; i ++ ) par[i][0] = -1 ;  
	predfs(0 , -1) ; 
}
long long Query(int S , int X[] , int T , int Y[]){
	L = R= 0 ; 
	for(int i = 0 ; i < S ; i ++ ){
		t.pb(X[i]) ; 
		q[R++] = X[i] ; 
	}
	for(int i = 0 ; i <T ; i ++ ){
		t.pb(Y[i]) ; mark[Y[i]] = 1 ; 
	}
	sort(all(t) , cmp) ; 
	for(int i = 0 ; i < T + S - 1 ; i ++ ){
		t.pb(lca(t[i] , t[i + 1])) ; 
	}t.pb(lca(t[T+S-1] , t[0])) ; 
	sort(all(t) , cmp) ; t.resize(unique(all(t)) - t.begin()) ; 
	for(auto u : t){
		d[u] = inf ; 
		while(s.size() && !( st[s.top()] < st[u] && ft[u] <= ft[s.top()] ) ) s.pop() ; 
		if(s.size()){
			g[u].pb({s.top() , dis[u] - dis[s.top()] }) ; 
			g[s.top()].pb({u , dis[u] - dis[s.top()] }) ; 
		}
		s.push(u) ; 
	}
	for(int i = 0 ; i < S ; i ++ ) d[X[i]] = 0 ; 
	ans = inf ; 
	while(L < R){
		int v = q[L++] ; 
		for(auto u : g[v]){
			if(d[u.X] > d[v] + u.Y){
				d[u.X] = d[v] + u.Y ; 
				q[R++] = u.X ; 
				if(mark[u.X])ans = min(ans , d[u.X]) ; 
			}
		}
	}
	for(auto u : t){
		g[u].clear() ; 
	}
	for(int i = 0 ; i < T ; i ++ ) mark[Y[i]] = 0 ; 
	t.clear() ; while(SZ(s)) s.pop() ; 
	return ans ; 
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24556 KB Output is correct
2 Correct 1374 ms 33856 KB Output is correct
3 Correct 1536 ms 33804 KB Output is correct
4 Correct 1420 ms 33904 KB Output is correct
5 Correct 1208 ms 34064 KB Output is correct
6 Correct 1002 ms 33784 KB Output is correct
7 Correct 1350 ms 33784 KB Output is correct
8 Correct 1415 ms 33900 KB Output is correct
9 Correct 1264 ms 34028 KB Output is correct
10 Correct 1828 ms 33772 KB Output is correct
11 Correct 1456 ms 33832 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24300 KB Output is correct
2 Correct 2626 ms 131312 KB Output is correct
3 Correct 3410 ms 134540 KB Output is correct
4 Correct 1891 ms 128712 KB Output is correct
5 Correct 3128 ms 163712 KB Output is correct
6 Correct 3651 ms 136280 KB Output is correct
7 Correct 3774 ms 55932 KB Output is correct
8 Correct 2049 ms 55360 KB Output is correct
9 Correct 2738 ms 60852 KB Output is correct
10 Correct 3890 ms 56876 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 24556 KB Output is correct
2 Correct 1374 ms 33856 KB Output is correct
3 Correct 1536 ms 33804 KB Output is correct
4 Correct 1420 ms 33904 KB Output is correct
5 Correct 1208 ms 34064 KB Output is correct
6 Correct 1002 ms 33784 KB Output is correct
7 Correct 1350 ms 33784 KB Output is correct
8 Correct 1415 ms 33900 KB Output is correct
9 Correct 1264 ms 34028 KB Output is correct
10 Correct 1828 ms 33772 KB Output is correct
11 Correct 1456 ms 33832 KB Output is correct
12 Correct 25 ms 24300 KB Output is correct
13 Correct 2626 ms 131312 KB Output is correct
14 Correct 3410 ms 134540 KB Output is correct
15 Correct 1891 ms 128712 KB Output is correct
16 Correct 3128 ms 163712 KB Output is correct
17 Correct 3651 ms 136280 KB Output is correct
18 Correct 3774 ms 55932 KB Output is correct
19 Correct 2049 ms 55360 KB Output is correct
20 Correct 2738 ms 60852 KB Output is correct
21 Correct 3890 ms 56876 KB Output is correct
22 Correct 6383 ms 142684 KB Output is correct
23 Correct 4518 ms 143732 KB Output is correct
24 Correct 5521 ms 146112 KB Output is correct
25 Correct 5389 ms 149216 KB Output is correct
26 Correct 5632 ms 140268 KB Output is correct
27 Correct 4654 ms 166752 KB Output is correct
28 Correct 3196 ms 136784 KB Output is correct
29 Correct 5469 ms 138940 KB Output is correct
30 Correct 5668 ms 138436 KB Output is correct
31 Correct 5552 ms 138860 KB Output is correct
32 Correct 2688 ms 62176 KB Output is correct
33 Correct 2338 ms 58144 KB Output is correct
34 Correct 3366 ms 54132 KB Output is correct
35 Correct 3364 ms 53868 KB Output is correct
36 Correct 3413 ms 54636 KB Output is correct
37 Correct 3541 ms 54540 KB Output is correct