Submission #49297

#	Time	Username	Problem	Language	Result	Execution time	Memory
49297		wzy	Factories (JOI14_factories)	C++11	33 / 100	6019 ms	135024 KiB

factories

        #include <bits/stdc++.h>
        #include "factories.h"
        using namespace std;
        #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;
        void pre_dfs(int x , int y){
        	pai[x] = y;
        	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(depth[x] > depth[y]) swap(x,y);
        	for(int j = 21 ; j >= 0 ; j--){
        		long long u = depth[y] - (1<<j);
        		if(u >= depth[x]){
        			y = lca[j][y];
        		}
        	}
        	if(x == y) return x;
        	for(int j = 21 ; j >= 0 ; j--){
        		if(lca[j][x] != lca[j][y] && lca[j][x] != -1){
        			x = lca[j][x] , y = lca[j][y];
        		}
        	}
        	return pai[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 );
        	pai[0] = -1;
        	for(int i = 0 ; i < N ; i++){
        		lca[0][i] = pai[i];
        	}
        	for(int j = 1 ; j < 22 ; j++){
        		for(int i = 0 ; i < N ; i++){
        			lca[j][i] = lca[j-1][lca[j-1][i]];
        		}
        	}
        	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);
        	stack<int> w;
        	int root = op[0];
        	w.push(op[0]);
        	for(int i = 1; i < pointer ; i++){
        	
        			while(w.size() && !(st[w.top()] <= st[op[i]] && st[op[i]] <= ed[w.top()])){
        				w.pop();
        			}
        			long long u =dist[op[i]] - dist[w.top()];
        			adj[op[i]].push_back(pii(w.top() , u));
        			adj[w.top()].push_back(pii(op[i] , u));
        			w.push(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:17:28: 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:75:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for(int j = 0 ; j < adj[x].size() ; j++){
                          ~~^~~~~~~~~~~~~~~

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