oj.uz

Submission #371996

# Submission time Handle Problem Language Result Execution time Memory
371996 2021-02-27T07:38:15 Z RohamIzadidoost Factories (JOI14_factories) C++14
100 / 100
 5848 ms 171912 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 48 ms 24556 KB Output is correct
2 Correct 1404 ms 33260 KB Output is correct
3 Correct 1301 ms 33248 KB Output is correct
4 Correct 1306 ms 33256 KB Output is correct
5 Correct 1237 ms 33516 KB Output is correct
6 Correct 1082 ms 33096 KB Output is correct
7 Correct 1221 ms 33292 KB Output is correct
8 Correct 1370 ms 33388 KB Output is correct
9 Correct 1189 ms 33568 KB Output is correct
10 Correct 980 ms 33296 KB Output is correct
11 Correct 1365 ms 33260 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24172 KB Output is correct
2 Correct 2592 ms 131236 KB Output is correct
3 Correct 3442 ms 134484 KB Output is correct
4 Correct 1888 ms 128720 KB Output is correct
5 Correct 3009 ms 163660 KB Output is correct
6 Correct 3773 ms 136116 KB Output is correct
7 Correct 3782 ms 55020 KB Output is correct
8 Correct 1935 ms 54336 KB Output is correct
9 Correct 2405 ms 60032 KB Output is correct
10 Correct 3861 ms 56088 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 24556 KB Output is correct
2 Correct 1404 ms 33260 KB Output is correct
3 Correct 1301 ms 33248 KB Output is correct
4 Correct 1306 ms 33256 KB Output is correct
5 Correct 1237 ms 33516 KB Output is correct
6 Correct 1082 ms 33096 KB Output is correct
7 Correct 1221 ms 33292 KB Output is correct
8 Correct 1370 ms 33388 KB Output is correct
9 Correct 1189 ms 33568 KB Output is correct
10 Correct 980 ms 33296 KB Output is correct
11 Correct 1365 ms 33260 KB Output is correct
12 Correct 23 ms 24172 KB Output is correct
13 Correct 2592 ms 131236 KB Output is correct
14 Correct 3442 ms 134484 KB Output is correct
15 Correct 1888 ms 128720 KB Output is correct
16 Correct 3009 ms 163660 KB Output is correct
17 Correct 3773 ms 136116 KB Output is correct
18 Correct 3782 ms 55020 KB Output is correct
19 Correct 1935 ms 54336 KB Output is correct
20 Correct 2405 ms 60032 KB Output is correct
21 Correct 3861 ms 56088 KB Output is correct
22 Correct 5356 ms 142120 KB Output is correct
23 Correct 4630 ms 143336 KB Output is correct
24 Correct 5144 ms 145796 KB Output is correct
25 Correct 5639 ms 153736 KB Output is correct
26 Correct 5697 ms 145320 KB Output is correct
27 Correct 4663 ms 171912 KB Output is correct
28 Correct 3400 ms 141936 KB Output is correct
29 Correct 5848 ms 144084 KB Output is correct
30 Correct 5778 ms 143508 KB Output is correct
31 Correct 5807 ms 143916 KB Output is correct
32 Correct 2818 ms 76148 KB Output is correct
33 Correct 2323 ms 72104 KB Output is correct
34 Correct 3433 ms 67588 KB Output is correct
35 Correct 3455 ms 67516 KB Output is correct
36 Correct 3570 ms 68240 KB Output is correct
37 Correct 4448 ms 68156 KB Output is correct