Submission #949647

#	Time	Username	Problem	Language	Result	Execution time	Memory
949647		amirhoseinfar1385	Factories (JOI14_factories)	C++17	100 / 100	5615 ms	240936 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10,lg=20;
struct yal{
	long long u,v,w;
	int getad(int fu){
		return (u^v^fu);
	}
}alle[maxn];
long long mainres,n,lca[lg][maxn],inf=1e16,vis1[maxn],vis2[maxn],timea,high[maxn];
pair<long long,long long>stf[maxn];
vector<long long>adj[maxn],adjt[maxn];
vector<long long>all;

pair<long long,long long> dfsres(long long u){
	//cout<<"chymisge "<<u<<endl;
	pair<long long,long long>ret=make_pair(inf,inf);
	if(vis1[u]){
		ret.first=high[u];
	}
	if(vis2[u]){
		ret.second=high[u];
	}
	mainres=min(mainres,ret.first+ret.second-2*high[u]);
	for(auto x:adjt[u]){
		pair<long long,long long>fake=dfsres(x);
		mainres=min(mainres,fake.first+ret.second-2*high[u]);
		mainres=min(mainres,fake.second+ret.first-2*high[u]);
		ret.first=min(fake.first,ret.first);
		ret.second=min(fake.second,ret.second);
	}
	return ret;
}

bool zird(long long u,long long v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

void dfs(long long u,long long par=-1){
	timea++;
	stf[u].first=timea;
	for(auto x:adj[u]){
		long long v=alle[x].getad(u);
		if(v==par){
			continue;
		}
		lca[0][v]=u;
		high[v]=high[u]+alle[x].w;
		dfs(v,u);
	}
	stf[u].second=timea;
}

void callca(){
	for(long long i=1;i<lg;i++){
		for(long long j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

long long getlca(long long u,long long v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(long long i=lg-1;i>=0;i--){
		if(lca[i][u]!=-1&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	//cout<<"nago: "<<u<<" "<<lca[0][u]<<" "<<zird(v,lca[0][u])<<endl;
	return lca[0][u];
}

void Init(int N, int A[], int B[], int D[]) {
	n=N;
	for(long long i=0;i<n;i++){
		alle[i].u=A[i];
		alle[i].v=B[i];
		alle[i].w=D[i];
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
	}
	for(int i=0;i<lg;i++){
		for(int j=0;j<maxn;j++){
			lca[i][j]=-1;
		}
	}
	dfs(0);
	callca();
	//assert(0);
}

bool cmp(long long a,long long b){
	return stf[a].first<stf[b].first;
}

long long calres(long long a,int A[],long long b,int B[]){
	for(long long i=0;i<a;i++){
		vis1[A[i]]=1;
	}
	for(long long i=0;i<b;i++){
		vis2[B[i]]=1;
	}
	mainres=inf;
	dfsres(0);
	for(auto x:all){
		vis1[x]=vis2[x]=0;
		adjt[x].clear();
	}
	all.clear();
	return mainres;
}

void create(long long a,int A[],long long b,int B[]){
	for(long long i=0;i<a;i++){
		all.push_back(A[i]);
	}
	for(long long i=0;i<b;i++){
		all.push_back(B[i]);
	}
	all.push_back(0);
	sort(all.begin(),all.end(),cmp);
	for(long long i=0;i<a+b;i++){
		all.push_back(getlca(all[i],all[i+1]));
	}
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	sort(all.begin(),all.end(),cmp);
	vector<long long>v={0};
	if(all[0]!=0){
		//cout<<"wtf:\n";
		for(auto x:all){
			//cout<<x<<" ";
		}
		//cout<<"\n";
		assert(0);
	}
	for(long long i=1;i<(long long)all.size();i++){
		while(stf[v.back()].second<stf[all[i]].first){
			v.pop_back();
		}
		adjt[v.back()].push_back(all[i]);
		v.push_back(all[i]);
	}
}

long long Query(int S, int X[], int T, int Y[]) {
//	//cout<<"wtf"<<endl;
	create(S,X,T,Y);
//	//cout<<"ha"<<endl;
	return calres(S,X,T,Y);	
}

Compilation message (stderr)

factories.cpp: In function 'void create(long long int, int*, long long int, int*)':
factories.cpp:137:12: warning: unused variable 'x' [-Wunused-variable]
  137 |   for(auto x:all){
      |            ^

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