Submission #922339

#	Time	Username	Problem	Language	Result	Execution time	Memory
922339		pcc	Roadside Advertisements (NOI17_roadsideadverts)	C++14	100 / 100	234 ms	11356 KiB

roadsideadverts

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 5e4+10;
int N,Q;
vector<pii> tree[mxn];
ll segtree[mxn*4];
int idx[mxn],par[mxn],sz[mxn],bs[mxn],link_top[mxn],dep[mxn],val[mxn],arr[mxn],cnt;
vector<pll> st;

void modify(int now,int l,int r,int s,int e){
	if(!segtree[now])return;
	if(l>=s&&e>=r){
		st.push_back(make_pair(now,segtree[now]));
		segtree[now] = 0;
		return;
	}
	int mid = (l+r)>>1;
	if(mid>=s)modify(now*2+1,l,mid,s,e);
	if(mid<e)modify(now*2+2,mid+1,r,s,e);
	st.push_back(make_pair(now,segtree[now]));
	segtree[now] = segtree[now*2+1]+segtree[now*2+2];
}
ll getval(int now,int l,int r,int s,int e){
	if(l>=s&&e>=r)return segtree[now];
	else if(!segtree[now])return 0ll;
	int mid = (l+r)>>1;
	if(mid>=e)return getval(now*2+1,l,mid,s,e);
	else if(mid<s)return getval(now*2+2,mid+1,r,s,e);
	else return getval(now*2+1,l,mid,s,e)+getval(now*2+2,mid+1,r,s,e);
}
void build(int now,int l,int r){
	if(l==r){
		segtree[now] = val[l];
		return;
	}
	int mid = (l+r)>>1;
	build(now*2+1,l,mid);
	build(now*2+2,mid+1,r);
	segtree[now] = segtree[now*2+1]+segtree[now*2+2];
	return;
}

void dfs1(int now){
	sz[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt.fs == par[now])continue;
		par[nxt.fs] = now;
		arr[nxt.fs] = nxt.sc;
		dep[nxt.fs] = dep[now]+1;
		dfs1(nxt.fs);
		sz[now] += sz[nxt.fs];
		if(!bs[now]||sz[bs[now]]<sz[nxt.fs])bs[now] = nxt.fs;
	}
	return;
}
void dfs2(int now,int top){
	idx[now] = ++cnt;
	val[cnt] = arr[now];
	link_top[now] = top;
	if(bs[now])dfs2(bs[now],top);
	for(auto nxt:tree[now]){
		if(nxt.fs == par[now]||nxt.fs == bs[now])continue;
		dfs2(nxt.fs,nxt.fs);
	}
	return;
}

ll lca(int a,int b){
	int ta = link_top[a],tb = link_top[b];
	ll re = 0;
	while(ta != tb){
		if(dep[ta]<dep[tb]){
			swap(a,b);
			swap(ta,tb);
		}
		re += getval(0,1,N,idx[ta],idx[a]);
		modify(0,1,N,idx[ta],idx[a]);
		a = par[ta];
		ta = link_top[a];
	}
	if(dep[a]>dep[b])swap(a,b);
	if(a != b){
		re += getval(0,1,N,idx[a]+1,idx[b]);
		modify(0,1,N,idx[a]+1,idx[b]);
	}
	return re;
}

void segdfs(int now,int l,int r){
	cout<<l<<' '<<r<<":"<<segtree[now]<<endl;
	if(l == r)return;
	int mid = (l+r)>>1;
	segdfs(now*2+1,l,mid);
	segdfs(now*2+2,mid+1,r);
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<N;i++){
		int a,b,c;
		cin>>a>>b>>c;
		a++,b++;
		tree[a].push_back({b,c});
		tree[b].push_back({a,c});
	}
	dep[1] = 1;
	dfs1(1);
	dfs2(1,1);
	build(0,1,N);
	/*
	for(int i = 1;i<=N;i++)cout<<idx[i]<<' ';cout<<endl;
	for(int i = 1;i<=N;i++)cout<<val[i]<<' ';cout<<endl;
	segdfs(0,1,N);

   */
	cin>>Q;
	while(Q--){
		int req[5];
		for(auto &i:req)cin>>i,i++;
		ll ans = 0;
		for(int i = 0;i<5;i++){
			for(int j = i+1;j<5;j++){
				ans += lca(req[i],req[j]);
			}
		}
		cout<<ans<<'\n';
		while(!st.empty()){
			segtree[st.back().fs] = st.back().sc;
			st.pop_back();
		}
	}
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 40 / 40
• Subtask 4: 30 / 30