Submission #345192

#	Time	Username	Problem	Language	Result	Execution time	Memory
345192		Kerim	Factories (JOI14_factories)	C++17	100 / 100	6868 ms	184324 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
#define MAXN 500009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,ll> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<PII>adj[MAXN],gr[MAXN];
const int LOG=19;
int in[MAXN],out[MAXN],P[MAXN][LOG];
int col[MAXN],lvl[MAXN],T;
ll val[MAXN];
void dfs1(int nd,int pr){
	in[nd]=++T;
	tr(it,adj[nd])
		if(it->ff!=pr){
			val[it->ff]=val[nd]+it->ss;
			lvl[it->ff]=lvl[nd]+1;
			P[it->ff][0]=nd;
			dfs1(it->ff,nd);	
		}
	out[nd]=T;
}
void Init(int N, int A[], int B[], int D[]) {
	for(int i=0;i<N-1;i++){
		int u=A[i],v=B[i],w=D[i];
		adj[u].pb(mp(v,w));	
		adj[v].pb(mp(u,w));
	}
	memset(col,-1,sizeof col);
	memset(P,-1,sizeof P);
	dfs1(0,-1);
	for(int j=1;j<LOG;j++)
		for(int i=0;i<N;i++)
			if(~P[i][j-1])
				P[i][j]=P[P[i][j-1]][j-1];
}
bool cmp(int x,int y){
	return (in[x]<in[y]);	
}
bool ata(int x,int y){
	return (in[x]<=in[y] and out[y]<=out[x]);
}
int LCA(int x,int y){
	if(lvl[x]<lvl[y])
		swap(x,y);
	for(int i=LOG-1;i>=0;i--)
		if(~P[x][i] and lvl[P[x][i]]>=lvl[y])
			x=P[x][i];
	if(x==y)return x;
	for(int i=LOG-1;i>=0;i--)
		if(~P[x][i] and P[x][i]!=P[y][i])
			x=P[x][i],y=P[y][i];
	return P[x][0];
}
const ll B=1e15;
ll dp[MAXN][2],ans;	
void dfs(int nd){
	dp[nd][0]=dp[nd][1]=B;
	if(~col[nd])dp[nd][col[nd]]=0;
	tr(it,gr[nd]){
		dfs(it->ff);
		umin(dp[nd][0],dp[it->ff][0]+it->ss);
		umin(dp[nd][1],dp[it->ff][1]+it->ss);
	}
	umin(ans,dp[nd][0]+dp[nd][1]);
}
long long Query(int S, int X[], int T, int Y[]) {
	vector<int>g;
	for(int i=0;i<S;i++)
		col[X[i]]=0,g.pb(X[i]);
	for(int i=0;i<T;i++)
		col[Y[i]]=1,g.pb(Y[i]);
	sort(all(g),cmp);vector<int>v=g;
	for(int i=0;i<int(g.size())-1;i++)
		v.pb(LCA(g[i],g[i+1]));
	sort(all(v),cmp);v.erase(unique(all(v)),v.end());
	stack<int>st;int root=v[0];
	tr(it,v){
		while(!st.empty() and !ata(st.top(),*it))
			st.pop();
		if(!st.empty())
			gr[st.top()].pb(mp(*it,val[*it]-val[st.top()]));
		st.push(*it);
	}
	ans=B;dfs(root);
	tr(it,v)gr[*it].clear();
	for(int i=0;i<S;i++)
		col[X[i]]=-1;
	for(int i=0;i<T;i++)
		col[Y[i]]=-1;
  	return ans;
}

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