Submission #953404

#	Time	Username	Problem	Language	Result	Execution time	Memory
953404		YassirSalama	Two Currencies (JOI23_currencies)	C++17	28 / 100	357 ms	67260 KiB

currencies

#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define int long long
const int MAXN=2e5+100;
const int LOGN=21;
vector<int> v[MAXN];
int depth[MAXN];
vector<int> c[MAXN];
int up[MAXN][LOGN+1];
vector<pair<int,int>> edges;
map<pair<int,int>,int> mp;
int p[MAXN];
int ff[MAXN];
void dfs(int node,int par){
	depth[node]=depth[par]+1;
	up[node][0]=par;
	p[node]=par;
	ff[node]=ff[par]+c[mp[{node,par}]].size();
	for(int i=1;i<LOGN;i++){
		up[node][i]=up[up[node][i-1]][i-1];
	}
	for(auto x:v[node]){
		if(x==par) continue;
		dfs(x,node);
	}
}
int LCA(int a,int b){
	if(depth[a]<depth[b]) swap(a,b);
	int d=depth[a]-depth[b];
	for(int i=LOGN-1;i>=0;i--){
		if((1<<i)&d){
			a=up[a][i];
		}
	}
	if(a==b) return a;
	for(int i=LOGN-1;i>=0;i--){
		if(up[a][i]!=up[b][i]){
			a=up[a][i];
			b=up[b][i];
		}
	}
	return up[a][0];
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,m,q;
cin>>n>>m>>q;
for(int i=0;i<n-1;i++){
	int a,b;
	cin>>a>>b;
	v[a].pb(b);
	v[b].pb(a);
	edges.pb({a,b});
	mp[{a,b}]=mp[{b,a}]=i;
}
int c1=0;
for(int i=0;i<m;i++){
	int t;
	int d;
	cin>>t>>d;
    t--;
    c1=d;
    int a=edges[t].F;
    int b=edges[t].S;
    c[t].pb(d);
}
for(int i=0;i<n;i++){
	sort(all(c[i]));
}
dfs(1,1);
while(q--){
	int a,b,x,y;
	cin>>a>>b>>x>>y;
	int l=LCA(a,b);
	int k=ff[a]+ff[b]-2*ff[l];
	// y/=c1;
	// vector<int> d;
	// while(a!=l){
	// 	int t=p[a];
	// 	for(auto x:c[mp[{a,t}]]) d.pb(x);
	// 	a=p[a];
	// }
	// while(b!=l){
	// 	int t=p[b];
	// 	for(auto x:c[mp[{b,t}]]) d.pb(x);
	// 	b=p[b];
	// }
	// assert((d.size())==k);
	// sort(all(d));
	int f=max(0LL,k-y/c1);
	int fe=0;
	// OVL(d," ")
	// dbg(fe,f,k,y)
	// for(auto e:d){
	// 	if(y>=e) y-=e;
	// 	else fe++;
	// }	
	// assert(fe==f);
	if(x>=f){
		cout<<x-f<<endl;
		continue;
	}else cout<<-1<<endl;
}
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:79:9: warning: unused variable 'a' [-Wunused-variable]
   79 |     int a=edges[t].F;
      |         ^
currencies.cpp:80:9: warning: unused variable 'b' [-Wunused-variable]
   80 |     int b=edges[t].S;
      |         ^
currencies.cpp:107:6: warning: unused variable 'fe' [-Wunused-variable]
  107 |  int fe=0;
      |      ^~

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