oj.uz

Submission #371917

# Submission time Handle Problem Language Result Execution time Memory
371917 2021-02-27T07:00:21 Z RohamIzadidoost Factories (JOI14_factories) C++14
33 / 100
 8000 ms 206836 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#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 = 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:2: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    2 | #pragma comment(linker, "/stack:200000000")
      | 
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:169:2: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  169 |  while(SZ(q)) q.pop() ; t.clear() ; while(SZ(s)) s.pop() ;
      |  ^~~~~
factories.cpp:169:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  169 |  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 51 ms 24684 KB Output is correct
2 Correct 1782 ms 34372 KB Output is correct
3 Correct 2061 ms 34384 KB Output is correct
4 Correct 1772 ms 34424 KB Output is correct
5 Correct 2044 ms 34692 KB Output is correct
6 Correct 1402 ms 34284 KB Output is correct
7 Correct 1811 ms 34412 KB Output is correct
8 Correct 1729 ms 34408 KB Output is correct
9 Correct 1723 ms 34668 KB Output is correct
10 Correct 1289 ms 34304 KB Output is correct
11 Correct 1876 ms 34380 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24300 KB Output is correct
2 Correct 3839 ms 174420 KB Output is correct
3 Correct 6122 ms 177560 KB Output is correct
4 Correct 3052 ms 171736 KB Output is correct
5 Correct 6141 ms 206836 KB Output is correct
6 Correct 6566 ms 179228 KB Output is correct
7 Correct 7160 ms 63980 KB Output is correct
8 Correct 3657 ms 63352 KB Output is correct
9 Correct 6259 ms 68932 KB Output is correct
10 Correct 6901 ms 64892 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 24684 KB Output is correct
2 Correct 1782 ms 34372 KB Output is correct
3 Correct 2061 ms 34384 KB Output is correct
4 Correct 1772 ms 34424 KB Output is correct
5 Correct 2044 ms 34692 KB Output is correct
6 Correct 1402 ms 34284 KB Output is correct
7 Correct 1811 ms 34412 KB Output is correct
8 Correct 1729 ms 34408 KB Output is correct
9 Correct 1723 ms 34668 KB Output is correct
10 Correct 1289 ms 34304 KB Output is correct
11 Correct 1876 ms 34380 KB Output is correct
12 Correct 24 ms 24300 KB Output is correct
13 Correct 3839 ms 174420 KB Output is correct
14 Correct 6122 ms 177560 KB Output is correct
15 Correct 3052 ms 171736 KB Output is correct
16 Correct 6141 ms 206836 KB Output is correct
17 Correct 6566 ms 179228 KB Output is correct
18 Correct 7160 ms 63980 KB Output is correct
19 Correct 3657 ms 63352 KB Output is correct
20 Correct 6259 ms 68932 KB Output is correct
21 Correct 6901 ms 64892 KB Output is correct
22 Execution timed out 8106 ms 184876 KB Time limit exceeded
23 Halted 0 ms 0 KB -