Submission #371904

#	Time	Username	Problem	Language	Result	Execution time	Memory
371904		RohamIzadidoost	Factories (JOI14_factories)	C++14	33 / 100	8092 ms	229304 KiB

factories

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#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
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 = 20 ;
ll h[maxn] , dis[maxn] , st[maxn] , cnt , ft[maxn] , par[lg][maxn]  , n  , d[maxn] , Q , ans , mark[maxn]; 
vec<pll> adj[maxn] , g[maxn];
vec<int> t ;
queue<int> q ; 
stack<int> s ; 
bool cmp(int i , 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[]){
	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() ; 
	return ans ; 
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:167:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  167 |  while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
      |  ^~~~~
factories.cpp:167:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  167 |  while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
      |                         ^

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 0 / 67