Submission #49301

#	Time	Username	Problem	Language	Result	Execution time	Memory
49301		wzy	Factories (JOI14_factories)	C++11	0 / 100	1785 ms	226816 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define pil pair<int, ll>
#define F first
#define S second
#define mp make_pair
#define pb push_back
int lca[22][500005] , st[500005] , ed[500005] , depth[500005] , t=0;
ll dist[500005] , dp[2][500005];
vector<pil> adj[500005];
bool one[500005];
bool inside(int x , int y){
	return (st[x] <= st[y] && ed[x] >= ed[y]);
}
int get_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(!inside(lca[j][x] , y)) x = lca[j][x];
	}
	return lca[0][x];
}
void compute(int x , int y){
	lca[0][x] = y;
	st[x] = ++t;
	for(int j = 1 ; j < 22 ; j++){
			lca[j][x] = lca[j-1][lca[j-1][x]];
	}
	for(int j = 0 ; j < adj[x].size() ; j++){
		pil u = adj[x][j];
		if(u.first == y) continue;
		depth[u.first] = depth[x] + 1;
		dist[u.first] = u.second + dist[x];
		compute(u.first, x);
	}
	ed[x] = t;
}
void Init(int N, int A[], int B[], int D[]){
	for(int i = 0 ; i  < N - 1 ; i++){
		adj[A[i]].push_back(pil(B[i] , D[i]));
		adj[B[i]].push_back(pil(A[i] , D[i]));
	}
	depth[0] = 0 , dist[0] = 0LL;
	compute(0 , 0);
	for(int i = 0 ; i < N ; i++){
		adj[A[i]].clear();
		adj[B[i]].clear();
	}
}

bool cmp(int a , int b){
	return st[a] < st[b];
}

ll ans;

void solve(int x , int y){
	for(auto u : adj[x]){
		if(u.first == y) continue;
		solve(u.first , x);
		ans = min(ans , dp[0][x] + dp[1][u.first] + u.second);
		ans = min(ans , dp[1][x] + dp[0][u.first] + u.second);
		dp[0][x] = min(dp[0][x] , dp[0][u.first] + u.second);
		dp[1][x] = min(dp[1][x] , dp[1][u.first] + u.second);
	}
}

ll Query(int S, int X[], int T, int Y[]){
	vector<int> optimal;
	for(int i = 0 ; i < S ; i++){
		if(!one[X[i]]){
			optimal.push_back(X[i]);
			one[X[i]] = 1;
			dp[0][X[i]] = 0;
			dp[1][X[i]] = (ll) 1e16;
		}
	}
	for(int i = 0 ; i < T ; i++){
		if(!one[Y[i]]){
			optimal.push_back(Y[i]);
			one[Y[i]] = 1;
			dp[0][Y[i]] = (ll) 1e16;
			dp[1][Y[i]] = 0;
		}
	}
	sort(optimal.begin() , optimal.end() , cmp);
	int Z = optimal.size();
	for(int i = 0 ; i < Z - 1 ; i++){
		int L = get_lca(optimal[i] , optimal[i+1]);
		if(!one[L]){
			optimal.push_back(get_lca(optimal[i] , optimal[i+1]));
			one[L] = 1;
			dp[0][L] = (ll) 1e16;
			dp[1][L] = (ll) 1e16;
		}
	}
	sort(optimal.begin() , optimal.end() , cmp);
	stack<int> sweepline;
	int root = optimal[0];
	sweepline.push(optimal[0]);
	for(int i = 1 ; i < optimal.size() ; i++){
		one[optimal[i]] = false;
		while(!inside(sweepline.top() , optimal[i])){
			sweepline.pop();
		}
		adj[optimal[i]].push_back(pil(sweepline.top() , dist[optimal[i]] - dist[sweepline.top()]));
		adj[sweepline.top()].push_back(pil(optimal[i] , dist[optimal[i]] - dist[sweepline.top()]));
		sweepline.push(optimal[i]);
	}
	ans = (ll) 1e16;
	solve(root, root);
	for(int i = 0 ; i < optimal.size() ; i++) adj[optimal[i]].clear(); 
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void compute(int, int)':
factories.cpp:31:20: 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:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1 ; i < optimal.size() ; i++){
                  ~~^~~~~~~~~~~~~~~~
factories.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < optimal.size() ; i++) adj[optimal[i]].clear(); 
                  ~~^~~~~~~~~~~~~~~~

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