Submission #49292

#	Time	Username	Problem	Language	Result	Execution time	Memory
49292		wzy	Factories (JOI14_factories)	C++11	0 / 100	6013 ms	147640 KiB

factories

	#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
	#include <stdio.h>
	#include <vector>
	#include <algorithm>
	#include <stack>
    #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] , vt[500005];
    int n , 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){
    	lca[0][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 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 j = 1 ; j < 22 ; j++){
    		for(int i = 0 ; i < N ; i++){
    			lca[j][i] = lca[j-1][lca[j-1][i]];
    		}
    	}
    }
     
    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 < vt[x].size() ; j++){
    		pii u = vt[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 < S ;i ++){
    		if(!jafoi[X[i]]){
    		dp[0][op[i]] = 0;
    		op[pointer++] = X[i];
    		jafoi[X[i]] = 1;
    	}
    	}
    	for(int i = 0 ; i < T ;i ++){
    		if(!jafoi[Y[i]]){
    		dp[1][op[i]] = 0;
    		op[pointer++] = Y[i];
    		jafoi[Y[i]] = 1;
    	}
    	}
    	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 = 0;
    	for(int i = 0 ; i < pointer ; i++){
    		if(w.empty()) w.push(op[i]) , root = op[i];
    		else{
    			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()];
    			vt[op[i]].push_back(pii(w.top() , u));
    			vt[w.top()].push_back(pii(op[i] , u));
    			w.push(op[i]);
    		}
    	}
    	ansz = 1000000000000000LL;
    	solve(root , root);
    	for(int i = 0 ; i < pointer; i++){
    		vt[op[i]].clear();
    		jafoi[op[i]] = false;
    	}
    	return ansz;
    }

Compilation message (stderr)

factories.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
  #pragma comment(linker, "/stack:200000000")
 
factories.cpp: In function 'void pre_dfs(int, int)':
factories.cpp:24:24: 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:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0 ; j < vt[x].size() ; j++){
                      ~~^~~~~~~~~~~~~~

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