oj.uz

Submission #371904

# Submission time Handle Problem Language Result Execution time Memory
371904 2021-02-27T06:53:26 Z RohamIzadidoost Factories (JOI14_factories) C++14
33 / 100
 8000 ms 229304 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 24428 KB Output is correct
2 Correct 1403 ms 43244 KB Output is correct
3 Correct 1573 ms 43224 KB Output is correct
4 Correct 1509 ms 43264 KB Output is correct
5 Correct 1338 ms 43500 KB Output is correct
6 Correct 1184 ms 43116 KB Output is correct
7 Correct 1403 ms 43192 KB Output is correct
8 Correct 1541 ms 43216 KB Output is correct
9 Correct 1431 ms 43500 KB Output is correct
10 Correct 1232 ms 43076 KB Output is correct
11 Correct 1483 ms 43216 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24300 KB Output is correct
2 Correct 3819 ms 196992 KB Output is correct
3 Correct 5693 ms 199384 KB Output is correct
4 Correct 2834 ms 194004 KB Output is correct
5 Correct 5499 ms 229304 KB Output is correct
6 Correct 6162 ms 201868 KB Output is correct
7 Correct 6471 ms 78300 KB Output is correct
8 Correct 3455 ms 77676 KB Output is correct
9 Correct 5213 ms 83400 KB Output is correct
10 Correct 6226 ms 79600 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 24428 KB Output is correct
2 Correct 1403 ms 43244 KB Output is correct
3 Correct 1573 ms 43224 KB Output is correct
4 Correct 1509 ms 43264 KB Output is correct
5 Correct 1338 ms 43500 KB Output is correct
6 Correct 1184 ms 43116 KB Output is correct
7 Correct 1403 ms 43192 KB Output is correct
8 Correct 1541 ms 43216 KB Output is correct
9 Correct 1431 ms 43500 KB Output is correct
10 Correct 1232 ms 43076 KB Output is correct
11 Correct 1483 ms 43216 KB Output is correct
12 Correct 26 ms 24300 KB Output is correct
13 Correct 3819 ms 196992 KB Output is correct
14 Correct 5693 ms 199384 KB Output is correct
15 Correct 2834 ms 194004 KB Output is correct
16 Correct 5499 ms 229304 KB Output is correct
17 Correct 6162 ms 201868 KB Output is correct
18 Correct 6471 ms 78300 KB Output is correct
19 Correct 3455 ms 77676 KB Output is correct
20 Correct 5213 ms 83400 KB Output is correct
21 Correct 6226 ms 79600 KB Output is correct
22 Correct 6790 ms 193760 KB Output is correct
23 Correct 6294 ms 194916 KB Output is correct
24 Execution timed out 8092 ms 197036 KB Time limit exceeded
25 Halted 0 ms 0 KB -