Submission #829547

#	Time	Username	Problem	Language	Result	Execution time	Memory
829547		CSQ31	Two Currencies (JOI23_currencies)	C++17	10 / 100	5065 ms	53192 KiB

currencies

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
/*
const int MAXN = 1e5+5;
int lf[MAXN],rg[MAXN],ndcnt = 0;
ll sum[MAXN];
int new_node(){
	ndcnt++;
	return ndcnt;
}
int new_node(int v){
	ndcnt++;
	sum[ndcnt] = sum[v];
	lf[ndcnt] = lf[v];
	rg[ndcnt] = rg[v];	
	return ndcnt;
}
int upd(int v,int pos,int l,int r,ll val){
	if(l==r){
		ndcnt++;
		sum[ndcnt]+=val;
		return ndcnt;
	}
	int tm = (l+r)/2;
	int u = new_node(v);
	if(pos<=tm){
		if(!lf[v])lf[v] = new_node();
		lf[u] = upd(lf[v],pos,l,tm,val);
	}else{
		if(!rg[v])rg[v] = new_node();
		rg[u] = upd(rg[v],pos,tm+1,r,val);
	}
	
	sum[u] = 0;
	if(lf[u])sum[u]+=sum[lf[u]];
	if(rg[u])sum[u]+=sum[rg[u]];
	return u;
}
int query(int a,int b,int l,int r,ll k){
	if(l==r)return l;
	int tm = (l+r)/2;
	if(!ch[0][a])ch[0][a] = new_node();
	if(!ch[0][b])ch[0][b] = new_node();
	
	if(sum[ch[0][b]] - sum[ch[0][a]])
	
} */
const int MAXN = 2e5+5;
vector<int>adj[MAXN];
int tin[MAXN],tout[MAXN],dep[MAXN],par[19][MAXN];
int timer = 0;
void dfs(int v,int u){
	tin[v] = ++timer;
	for(int x:adj[v]){
	    if(x == u)continue;	
	    par[0][x] = v;
	    dep[x] = dep[v]+1;
	    for(int i=1;i<=18;i++){
			par[i][x] = par[i-1][par[i-1][x]];
		}
		dfs(x,v);
	}
	tout[v] = ++timer;
}
bool ancestor(int v,int u){return(tin[v] >= tin[u] && tout[u] >= tout[v]);}//is u an ancestor of v?
int lca(int v,int u){
	if(dep[v] > dep[u])swap(u,v);
	int dist = dep[u]-dep[v];
	for(int i=0;dist;i++,dist>>=1){
		if(dist&1)u = par[i][u];
	}
	if(u == v)return u;
	for(int i=18;i>=0;i--){
		if(par[i][v] != par[i][u]){
			u = par[i][u];
			v = par[i][v];
		}
	}
	return par[0][v];
}
int cost[MAXN];
int main()
{
	owo
	int n,m,q;
	cin>>n>>m>>q;
	vector<pii>ed(n),C(m);
	for(int i=1;i<n;i++)cin>>ed[i].fi>>ed[i].se;
	for(int i=0;i<m;i++)cin>>C[i].se>>C[i].fi;
	
	vii p(n);
	sort(all(C));
	int N = n;
	for(int i=0;i<m;i++){
		N++; //label this guy as N
		p[C[i].se].pb(N);
		cost[N] = C[i].fi;
	}
	for(int i=1;i<n;i++){
		int a = ed[i].fi;
		int b = ed[i].se;
		for(int x:p[i]){
			adj[a].pb(x);
			adj[x].pb(a);
			a = x;
		}
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1,-1);
	while(q--){
		int s,t,x;
		ll y;
		cin>>s>>t>>x>>y;
		int v = lca(s,t);
		vector<int>path;
		while(s!=v){
			if(s>n)path.pb(s);
			s = par[0][s];
		}
		while(t!=v){
			if(t>n)path.pb(t);
			t = par[0][t];
		}
		sort(all(path));
		int cnt = sz(path);
		for(int x:path){
			if(y>=cost[x]){
				y-=cost[x];
				cnt--;
			}else break;
		}
		if(x>=cnt)cout<<x-cnt<<'\n';
		else cout<<-1<<'\n';
	}
	
	
	
	
}

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