제출 #949132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949132		ting39	Two Currencies (JOI23_currencies)	C++17	28 / 100	486 ms	40028 KiB

currencies

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
vector<vector<int>> g,jump;
vector<int> dep,dis,c;
int cost;
void dfs(int pre,int pos){
	for(int i:g[pos]){
		if(i==pre) continue;
		jump[i][0]=pos;
		dep[i]=dep[pos]+1;
		dis[i]=dis[pos]+c[i];
		dfs(pos,i);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	int diff=dep[x]-dep[y],cnt=0;
	while(diff){
		if(diff&1){
			x=jump[x][cnt];
		}
		cnt++;
		diff>>=1;
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--){
		if(jump[x][i]!=jump[y][i]){
			x=jump[x][i];
			y=jump[y][i];
		}
	}
	return jump[x][0];
}
int sol(int x,int y){
	return dis[x]+dis[y]-2*dis[lca(x,y)];
}
signed main(){
	int n,m,q;
	cin>>n>>m>>q;
	g.resize(n);
	dep.resize(n);
	dis.resize(n);
	c.resize(n);
	jump.resize(n,vector<int>(20));
	vector<pii> ed(n-1);
	for(int i=0;i<n-1;i++){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		ed[i]={a,b};
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0,0);
	while(m--){
		int a,b;
		cin>>a>>b;
		cost=b;
		a--;
		pii e=ed[a];
		if(dep[e.F]<dep[e.S]) swap(e.F,e.S);
		c[e.F]++;
	}
	dfs(0,0);
	//for(int i:dep) cout<<i<<' ';cout<<endl;
	for(int i=1;i<20;i++){
		for(int j=0;j<n;j++){
			jump[j][i]=jump[jump[j][i-1]][i-1];
		}
	}
	while(q--){
		int s,t,x,y;
		cin>>s>>t>>x>>y;
		s--;
		t--;
		int tmp=sol(s,t);
		//cout<<tmp<<endl;
		tmp-=y/cost;
		tmp=max(0LL,tmp);
		x-=tmp;
		if(x<0){
			cout<<-1<<endl;
		}
		else cout<<x<<endl;
	}
}

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