oj.uz

Submission #371924

# Submission time Handle Problem Language Result Execution time Memory
371924 2021-02-27T07:03:54 Z RohamIzadidoost Factories (JOI14_factories) C++14
33 / 100
 8000 ms 206736 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 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(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[]){
	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 45 ms 24556 KB Output is correct
2 Correct 1806 ms 33820 KB Output is correct
3 Correct 1774 ms 33796 KB Output is correct
4 Correct 1686 ms 33912 KB Output is correct
5 Correct 1809 ms 34084 KB Output is correct
6 Correct 1256 ms 33772 KB Output is correct
7 Correct 1766 ms 33772 KB Output is correct
8 Correct 1803 ms 33976 KB Output is correct
9 Correct 1708 ms 34148 KB Output is correct
10 Correct 1300 ms 33772 KB Output is correct
11 Correct 1702 ms 33896 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24300 KB Output is correct
2 Correct 3956 ms 174324 KB Output is correct
3 Correct 6233 ms 177480 KB Output is correct
4 Correct 2919 ms 171740 KB Output is correct
5 Correct 6665 ms 206736 KB Output is correct
6 Correct 6842 ms 179180 KB Output is correct
7 Correct 7728 ms 63572 KB Output is correct
8 Correct 3583 ms 62988 KB Output is correct
9 Correct 6419 ms 68488 KB Output is correct
10 Correct 7104 ms 64792 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24556 KB Output is correct
2 Correct 1806 ms 33820 KB Output is correct
3 Correct 1774 ms 33796 KB Output is correct
4 Correct 1686 ms 33912 KB Output is correct
5 Correct 1809 ms 34084 KB Output is correct
6 Correct 1256 ms 33772 KB Output is correct
7 Correct 1766 ms 33772 KB Output is correct
8 Correct 1803 ms 33976 KB Output is correct
9 Correct 1708 ms 34148 KB Output is correct
10 Correct 1300 ms 33772 KB Output is correct
11 Correct 1702 ms 33896 KB Output is correct
12 Correct 23 ms 24300 KB Output is correct
13 Correct 3956 ms 174324 KB Output is correct
14 Correct 6233 ms 177480 KB Output is correct
15 Correct 2919 ms 171740 KB Output is correct
16 Correct 6665 ms 206736 KB Output is correct
17 Correct 6842 ms 179180 KB Output is correct
18 Correct 7728 ms 63572 KB Output is correct
19 Correct 3583 ms 62988 KB Output is correct
20 Correct 6419 ms 68488 KB Output is correct
21 Correct 7104 ms 64792 KB Output is correct
22 Correct 7846 ms 184884 KB Output is correct
23 Correct 7561 ms 185892 KB Output is correct
24 Execution timed out 8031 ms 187712 KB Time limit exceeded
25 Halted 0 ms 0 KB -