Submission #50705

#	Time	Username	Problem	Language	Result	Execution time	Memory
50705		wzy	Factories (JOI14_factories)	C++11	15 / 100	6060 ms	114004 KiB

factories

		#include <bits/stdc++.h>
		#include "factories.h"
		using namespace std;
		#pragma GCC optimize ("Ofast")
		#define pii pair<int,long long>
		#define F first
		#define S second
		#define pb push_back
		bool jafoi[500005];
		vector<pii> adj[500005] ;
		int n , pai[500005] , lca[22][500005] , depth[500005] , st[500005] , t= 0 , ed[500005] ;
		long long  dist[500005] , dp[2][500005];
		int op[1000000];
		int pointer = 0;
		bool inside(int u , int v){
			return (st[u] <= st[v] && ed[u] >= ed[v]);
		}
		void pre_dfs(int x , int y){
			lca[0][x] = y;
			for(int j = 1 ; j< 22 ; j++){
				if(lca[j-1][x] != -1){
					lca[j][x] = lca[j-1][lca[j-1][x]];
				}
			}
			st[x] = ++t;
			for(int j = 0 ; j < adj[x].size() ; j++){
				pii u = adj[x][j];
				if(u.first == y) continue;
				dist[u.first] = dist[x] + u.second;
				depth[u.first] = depth[x] + 1;
				pre_dfs(u.first, x);
			}
			ed[x] = t;
		}
		 
		int query_lca(int x , int y){
			if(inside(x,y)) return x;
			if(inside(y,x)) return y;
			for(int j = 21 ; j >= 0 ; j--){
				if(lca[j][x] != -1 && !(inside(lca[j][x] , y))) x = lca[j][x];
			}
			return lca[0][x];
		}
		 
		 
		 
		void Init(int N, int A[], int B[], int D[]){
			n = N;
			for(int i = 0 ; i < N - 1 ; i++){
				adj[A[i]].pb(pii(B[i] , D[i]));
				adj[B[i]].pb(pii(A[i] , D[i]));
			}
			depth[0] = 0 , dist[0] = 0;
			pre_dfs(0 , - 1 );
			for(int i = 0 ; i < N  - 1; i++){
				adj[A[i]].clear() , adj[B[i]].clear();
			}
		}
		 
		bool cmp(int a , int  b){
			return st[a] < st[b];
		}
		 
		long long ansz = 0;
		 
		void solve(int x , int y){
			for(int j = 0 ; j < adj[x].size() ; j++){
				pii u = adj[x][j];
				if(u.F == y) continue;
				solve(u.F, x);
				ansz = min(ansz , min(dp[0][x] + dp[1][u.F] + u.S ,  dp[1][x] + dp[0][u.F] + u.S));
				dp[0][x] = min(dp[0][x] , dp[0][u.F] + u.S);
				dp[1][x] = min(dp[1][x] , dp[1][u.F] + u.S);
			}
			return ;
		}
		 
		long long Query(int S , int X[] , int T , int Y[]){
			pointer = 0;
			for(int i = 0 ; i < max(S,T) ;i ++){
				if(!jafoi[X[i]] && i < S){
					op[pointer++] = X[i];
					jafoi[X[i]] = 1;
					dp[0][X[i]] = 0;
					dp[1][X[i]] = 1000000000000000LL;
				}
				if(!jafoi[Y[i]] && i < T){
					op[pointer++] = Y[i];
					jafoi[Y[i]] = 1;
					dp[1][Y[i]] = 0;
					dp[0][Y[i]] = 1000000000000000LL;
				}
			}
			sort(op , op + pointer , cmp);
			int Z = (pointer)- 1;
			for(int i = 0 ; i < Z ; i++){
				int L = query_lca(op[i] , op[i+1]);
				if(!jafoi[L]){
				dp[0][L] = 1000000000000000LL;
				dp[1][L] = 1000000000000000LL;
				op[pointer++] = L;		
				jafoi[L] = 1;
				}
			}
			sort(op , op + pointer , cmp);
			vector<int> w;
			int root ;
			for(int i = 0; i < pointer ; i++){
					if(w.size() == 0){
						root = op[i];
						w.push_back(op[i]);
						continue;
					}
					while(w.size() && !(inside(w.back() , op[i]))){
						w.pop_back();
					}
					long long u =dist[op[i]] - dist[w.back()];
					adj[op[i]].push_back(pii(w.back() , u));
					adj[w.back()].push_back(pii(op[i] , u));
					w.push_back(op[i]);
				
			}
			ansz = 1000000000000000LL;
			solve(root , root);
			for(int i = 0 ; i < pointer; i++){
				adj[op[i]].clear();
				jafoi[op[i]] = false;
			}
			return ansz;
		}

Compilation message (stderr)

factories.cpp: In function 'void pre_dfs(int, int)':
factories.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < adj[x].size() ; j++){
                    ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void solve(int, int)':
factories.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0 ; j < adj[x].size() ; j++){
                    ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:124:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
    solve(root , root);
    ~~~~~^~~~~~~~~~~~~

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