Submission #28819

#	Time	Username	Problem	Language	Result	Execution time	Memory
28819		PrOAhMeT	Factories (JOI14_factories)	C++14	15 / 100	6000 ms	111864 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=500005;
vector<pii> v[MAXN];
int head[MAXN],par[MAXN],in[MAXN],out[MAXN],tme,sub[MAXN],who[MAXN],vis[MAXN*4],n,sum;
stack<int> st;
LL f[MAXN*4],lazy[MAXN*4],val[MAXN];

int dfs(int x,int y,LL path) {

	val[x]=path;
	sub[x]=1;
	par[x]=y;
	for(int i=0;i<(int)v[x].size();++i) {
		if(v[x][i].st!=y)
			sub[x]+=dfs(v[x][i].st,x,path+v[x][i].nd);
	}
	return sub[x];

}

void hld(int x,int y) {

	in[x]=++tme;
	who[tme]=x;
	if(v[x][0].st==y&&(int)v[x].size()>1)
		swap(v[x][0].st,v[x][1].st);
	for(int i=0;i<(int)v[x].size();++i)
		if(v[x][i].st!=y&&sub[v[x][i].st]>sub[v[x][0].st])
			swap(v[x][0],v[x][i]);
	for(int i=0;i<(int)v[x].size();++i) {
		if(v[x][i].st==y)
			continue;
		if(i==0)
			head[v[x][i].st]=head[x];
		else head[v[x][i].st]=v[x][i].st;
		hld(v[x][i].st,x);
	}
	out[x]=tme;

}

void push(int x,int l,int r) {

	f[x]=min(f[x],lazy[x]-2*val[who[r]]);
	lazy[x*2]=min(lazy[x*2],lazy[x]);
	lazy[x*2+1]=min(lazy[x*2+1],lazy[x]);
	lazy[x]=1e17;

}

void upd(int x,int l,int r,int ll,int rr,LL v) {

	if(lazy[x]!=1e17) 
		push(x,l,r);
	if(!vis[x]) {
		vis[x]=1;
		st.push(x);
	}
	if(l>rr||r<ll)
		return;
	if(l>=ll&&r<=rr) {
		lazy[x]=v;
		push(x,l,r);
		return;
	}
	int md=(l+r)/2;
	upd(x*2,l,md,ll,rr,v);
	upd(x*2+1,md+1,r,ll,rr,v);
	f[x]=min(f[x*2],f[x*2+1]);

}

LL que(int x,int l,int r,int ll,int rr) {

	if(lazy[x]!=1e17) 
		push(x,l,r);
	if(!vis[x]) {
		vis[x]=1;
		st.push(x);
	}
	if(l>rr||r<ll)
		return 1e17;
	if(l>=ll&&r<=rr)
		return f[x];
	int md=(l+r)/2;
	return min(que(x*2,l,md,ll,rr),que(x*2+1,md+1,r,ll,rr));

}

LL find(int x) {

	LL ret=1e17;
	while(x!=-1) {
		ret=min(ret,que(1,0,n-1,in[head[x]],in[x]));
		x=par[head[x]];
	}
	return ret;

}


void update(int x,LL v) {

	while(x!=-1) {
		upd(1,0,n-1,in[head[x]],in[x],v);
		x=par[head[x]];
	}

}

void Init(int N, int A[], int B[], int D[]) {

	n=N;
	for(int i=0;i<n-1;++i) {
		v[A[i]].pb(mp(B[i],D[i]));
		v[B[i]].pb(mp(A[i],D[i]));
	}
	dfs(0,-1,0);
	head[0]=0;
	hld(0,0);
	for(int i=0;i<MAXN*4;++i)
		f[i]=lazy[i]=1e17;

}

long long Query(int s, int x[], int tt, int y[]) {
  
	LL ret=1e17;
	for(int i=0;i<tt;++i)
		update(y[i],val[y[i]]);
	for(int i=0;i<s;++i)
		ret=min(ret,find(x[i])+val[x[i]]);
	int t;
	sum+=st.size();
	while(!st.empty()) {
		t=st.top();
		st.pop();
		vis[t]=0;
		f[t]=lazy[t]=1e17;
		if(t*2<MAXN*4)
			lazy[t*2]=1e17;
		if(t*2+1<MAXN*4)
			lazy[t*2+1]=1e17;
	}
	assert(sum<600000000);
	return ret;

}

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