Submission #50739

#	Time	Username	Problem	Language	Result	Execution time	Memory
50739		wzy	Factories (JOI14_factories)	C++11	0 / 100	6088 ms	189496 KiB

factories

#include"factories.h"
#include <bits/stdc++.h>
using namespace std;

/*
MAGIA DO GATINHO 
PARA FAZER SEU CODE
PASSAR NO JUDGEZINHO 
  ∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
　　　　　　　　　.• ´¸.•*´¨) ¸.•*¨)
　　　　　　　　　　(¸.•´ (¸.•'* ☆
*/


long long dist[500005] , dp[2][500005] , depth[500005]; 
int  st[500005] , ed[500005] , lca[22][500005] , n , T = 0;
vector<pair<int,int> > adj[500005];

void dfs(int x , int y){
	st[x] = ++T;
	if(x!=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]];
		}
	}
	for(int i = 0 ; i < adj[x].size() ; i++){
		if(adj[x][i].first == y) continue;
		depth[adj[x][i].first] = depth[x] + 1;
		dist[adj[x][i].first] = dist[x] + adj[x][i].second; 
		dfs(adj[x][i].first, x);
	}
	ed[x] = T;
}


bool inside(int x , int y){ // olha se y ta na subtree de x
	return (st[x] <= st[y] && ed[x] >= ed[y]);

}

int lcaQ(int x , int y){
	if(inside(x,y)) return x;
	else 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];
}

long long ansz = 0;

long long get_dist(int x , int y){
	long long ans = dist[x] + dist[y] - 2*dist[lcaQ(x,y)];
	return ans;
}

void Init(int N, int A[], int B[], int D[]){	
	 n = N;
	 T = 0 ;
	 for(int i = 0 ; i < N ; i ++){
	 	adj[i].clear();
	 }
	 for(int i = 0 ; i < n - 1; i ++){
	 	adj[A[i]].push_back(pair<int,int>(B[i] , D[i]));
	 	adj[B[i]].push_back(pair<int,int>(A[i] , D[i]));
	 }
	 for(int i = 0; i < n ; i++)
	 	for(int j = 0 ; j < 22 ; j++) lca[j][i] = -1;
	 dist[0] = 0;
	 dfs(0 , 0 );
}
bool fl = 0;


vector<pair<int, int> > v_tree[500005];

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

bool vis[500005];

void solve(int x , int y){
	vis[x] = true;
	for(auto p : v_tree[x]){
		if(vis[p.first]) continue;
		solve(p.first, x);
		ansz = min(ansz , min(dp[0][x] + dp[1][p.first] + p.second , dp[1][x] + dp[0][p.first] + p.second));
		dp[0][x] = min(dp[0][x] , dp[0][p.first] + p.second);
		dp[1][x] = min(dp[1][x] , dp[1][p.first] + p.second);
	}
}

long long Query(int S, int X[], int T, int Y[]){
	vector<int> sweep;
	vector<int> loltree;
	for(int i = 0 ; i < S ; i ++){
		sweep.push_back(X[i]);
		loltree.push_back(X[i]);
	}for(int i = 0 ; i < T ; i ++){
		sweep.push_back(Y[i]);
		loltree.push_back(Y[i]);
	}
	sort(sweep.begin() , sweep.end() , cmp);
	for(int i = 0 ; i < ((int)sweep.size()) - 1 ; i++){
		loltree.push_back(lcaQ(sweep[i] , sweep[i+1]));
	}
	sort(loltree.begin() , loltree.end());
	loltree.resize(unique(loltree.begin() , loltree.end()) - loltree.begin());
	sort(loltree.begin() , loltree.end() , cmp);
	for(int i = 0 ; i < loltree.size() ; i++){
		dp[0][loltree[i]] = (long long) 1e18;
		dp[1][loltree[i]] = (long long) 1e18;
	}
	for(int i = 0 ; i < S ;i  ++){
		dp[0][X[i]] = 0;
	}
	for(int i = 0 ; i < T ; i++){
		dp[1][Y[i]] = 0;
	}
	int root = loltree.front();
	vector<int> sline;
	sline.push_back(root);
	for(int i =  1 ; i < loltree.size() ; i++){
		while(!inside(sline.back() , loltree[i])) sline.pop_back();
		v_tree[sline.back()].push_back(pair<int,int>(loltree[i] , get_dist(loltree[i] , sline.back())));
		v_tree[loltree[i]].push_back(pair<int,int>(sline.back() , get_dist(loltree[i] , sline.back())));
		sline.push_back(loltree[i]);
	}
	ansz = (long long) 1e18;
	solve(root, root);
	for(int i = 0 ; i < loltree.size() ; i++){
		v_tree[loltree[i]].clear();
		vis[loltree[i]] = false;
	}
	return ansz;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[x].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < loltree.size() ; i++){
                  ~~^~~~~~~~~~~~~~~~
factories.cpp:128:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i =  1 ; i < loltree.size() ; i++){
                   ~~^~~~~~~~~~~~~~~~
factories.cpp:136:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < loltree.size() ; i++){
                  ~~^~~~~~~~~~~~~~~~

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