oj.uz

Submission #371938

# Submission time Handle Problem Language Result Execution time Memory
371938 2021-02-27T07:08:33 Z RohamIzadidoost Factories (JOI14_factories) C++14
33 / 100
 8000 ms 163688 KB 
#include<bits/stdc++.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
#include<factories.h>
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]; 
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] ; 
	}
	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] ; 
		//////////////////////////////////////////
for(int i = 0 ; i < S ; i ++ ){
		t.pb(X[i]) ; 
		q.push(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(SZ(q)){
		int v = q.front() ; 
		q.pop() ;
		for(auto u : g[v]){
			if(d[u.X] > d[v] + u.Y){
				d[u.X] = d[v] + u.Y ; 
				q.push(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 ; 
	while(SZ(q)) q.pop() ; 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 49 ms 24428 KB Output is correct
2 Correct 1643 ms 33280 KB Output is correct
3 Correct 1629 ms 33232 KB Output is correct
4 Correct 1849 ms 33312 KB Output is correct
5 Correct 1504 ms 33516 KB Output is correct
6 Correct 1330 ms 33132 KB Output is correct
7 Correct 1764 ms 33260 KB Output is correct
8 Correct 1585 ms 33544 KB Output is correct
9 Correct 1555 ms 33644 KB Output is correct
10 Correct 1234 ms 33172 KB Output is correct
11 Correct 1677 ms 33260 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24172 KB Output is correct
2 Correct 3913 ms 131248 KB Output is correct
3 Correct 5936 ms 134484 KB Output is correct
4 Correct 2980 ms 128760 KB Output is correct
5 Correct 5890 ms 163688 KB Output is correct
6 Correct 6237 ms 136148 KB Output is correct
7 Correct 5713 ms 55020 KB Output is correct
8 Correct 3155 ms 54352 KB Output is correct
9 Correct 5588 ms 59824 KB Output is correct
10 Correct 6361 ms 56172 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 24428 KB Output is correct
2 Correct 1643 ms 33280 KB Output is correct
3 Correct 1629 ms 33232 KB Output is correct
4 Correct 1849 ms 33312 KB Output is correct
5 Correct 1504 ms 33516 KB Output is correct
6 Correct 1330 ms 33132 KB Output is correct
7 Correct 1764 ms 33260 KB Output is correct
8 Correct 1585 ms 33544 KB Output is correct
9 Correct 1555 ms 33644 KB Output is correct
10 Correct 1234 ms 33172 KB Output is correct
11 Correct 1677 ms 33260 KB Output is correct
12 Correct 24 ms 24172 KB Output is correct
13 Correct 3913 ms 131248 KB Output is correct
14 Correct 5936 ms 134484 KB Output is correct
15 Correct 2980 ms 128760 KB Output is correct
16 Correct 5890 ms 163688 KB Output is correct
17 Correct 6237 ms 136148 KB Output is correct
18 Correct 5713 ms 55020 KB Output is correct
19 Correct 3155 ms 54352 KB Output is correct
20 Correct 5588 ms 59824 KB Output is correct
21 Correct 6361 ms 56172 KB Output is correct
22 Correct 7546 ms 142132 KB Output is correct
23 Correct 7143 ms 143344 KB Output is correct
24 Execution timed out 8083 ms 145584 KB Time limit exceeded
25 Halted 0 ms 0 KB -