제출 #1272688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272688		PieArmy	Two Currencies (JOI23_currencies)	C++20	100 / 100	514 ms	33720 KiB

currencies

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

typedef pair<ll,ll> pl;

pl operator+(const pl x,const pl y){
	return pl{x.fr+y.fr,x.sc+y.sc};
}

struct Fen{
	int n;
	vector<pl>tree;
	void init(int N){
		n=N;
		tree.resize(0);
		tree.resize(n+1,pl{0,0});
	}
	void update(int tar,pl x){
		while(tar<=n){
			tree[tar]=tree[tar]+x;
			tar+=(tar&-tar);
		}
	}
	pl query(int tar){
		pl res={0,0};
		while(tar>0){
			res=res+tree[tar];
			tar-=(tar&-tar);
		}
		return res;
	}
};

int n,m,q;
vector<int>komsu[100023];
pl road[100023],check[100023];
int s[100023],t[100023];
int us[100023];
ll gold[100023],silv[100023];

int par[100023][17];
int in[100023],out[100023];
int tim=1;
Fen fen;

void dfs(int pos){
	for(int i=1;i<17;i++){
		par[pos][i]=par[par[pos][i-1]][i-1];
	}
	in[pos]=tim++;
	for(int x:komsu[pos]){
		if(x==par[pos][0])continue;
		par[x][0]=pos;
		dfs(x);
	}
	out[pos]=tim++;
}

int lca(int x,int y){
	if(in[x]<=in[y]&&out[x]>in[y])return x;
	for(int i=17-1;i>=0;i--){
		if(in[par[x][i]]<=in[y]&&out[par[x][i]]>in[y])continue;
		x=par[x][i];
	}
	return par[x][0];
}

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>m>>q;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
		road[i]={x,y};
	}
	for(int i=1;i<=m;i++){
		cin>>check[i].sc>>check[i].fr;
	}
	for(int i=1;i<=q;i++){
		cin>>s[i]>>t[i]>>gold[i]>>silv[i];
	}
	sort(check+1,check+m+1);
	par[1][0]=1;
	dfs(1);
	for(int i=1;i<n;i++){
		if(in[road[i].fr]<in[road[i].sc]){
			swap(road[i].fr,road[i].sc);
		}
	}
	for(int i=1;i<=m;i++){
		check[i].sc=road[check[i].sc].fr;
	}
	for(int i=1;i<=q;i++){
		us[i]=lca(s[i],t[i]);
	}
	queue<pair<pl,vector<int>>>Q;
	{
		vector<int>v(q);
		iota(v.begin(),v.end(),1);
		Q.push({{0,m},v});
	}
	int ind=m+1;
	while(Q.size()){
		int l=Q.front().fr.fr,r=Q.front().fr.sc;
		vector<int>v=Q.front().sc;
		Q.pop();
		if(!v.size())continue;
		int mi=(l+r+1)/2;
		if(ind>mi){
			fen.init(tim);
			for(int i=1;i<=m;i++){
				fen.update(in[check[i].sc],{0,1});
				fen.update(out[check[i].sc],{0,-1});
			}
			ind=0;
		}
		while(ind<mi){
			ind++;
			fen.update(in[check[ind].sc],{check[ind].fr,-1});
			fen.update(out[check[ind].sc],{-check[ind].fr,1});
		}
		if(l==r){
			for(int x:v){
				gold[x]-=fen.query(in[s[x]]).sc+fen.query(in[t[x]]).sc-2*fen.query(in[us[x]]).sc;
			}
			continue;
		}
		vector<int>sag,sol;
		for(int x:v){
			if(silv[x]>=fen.query(in[s[x]]).fr+fen.query(in[t[x]]).fr-2*fen.query(in[us[x]]).fr){
				sol.pb(x);
			}
			else sag.pb(x);
		}
		v.clear();
		Q.push({{l,mi-1},sag});
		Q.push({{mi,r},sol});
	}
	for(int i=1;i<=q;i++){
		if(gold[i]<0)cout<<-1<<endl;
		else cout<<gold[i]<<endl;
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32