Submission #851574

#TimeUsernameProblemLanguageResultExecution timeMemory
851574willychanTwo Currencies (JOI23_currencies)C++14
0 / 100
3 ms6488 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; //#include<bits/extc++.h> //__gnu_pbds const int N = 1e5+5; vector<pair<int,int> > side[N]; vector<pair<int,int> > edgeset; pair<int,int> father[N][20]; int dep[N]; void dfs(int c){ for(auto i : side[c]){ if(father[i.first][0].first==0) { dep[i.first] = dep[c]+1; father[i.first][0] = {c,i.second}; dfs(i.first); } } } int get(int a,int b){ if(a==b) return 0; ll sum =0; if(dep[a]>dep[b]) swap(a,b); if(dep[b]>dep[a]){ for(int j=19;j>=0;j--){ if(dep[father[b][j].first]>dep[a]){ sum+=father[b][j].second; b = father[b][j].first; } } sum+=father[b][0].second; b = father[b][0].first; } assert(dep[a]==dep[b]); if(a==b) return sum; for(int j=19;j>=0;j--){ if(father[a][j].first!=father[b][j].first){ sum+=father[a][j].second; sum+=father[b][j].second; a=father[a][j].first; b=father[b][j].first; } } sum+=father[a][0].second; sum+=father[b][0].second; return sum; } int main(){ ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n,m,q;cin>>n>>m>>q; for(int i=0;i<n-1;i++){ int a,b;cin>>a>>b; side[a].push_back({b,0}); side[b].push_back({a,0}); edgeset.push_back({a,side[a].size()-1}); edgeset.push_back({b,side[b].size()-1}); } int C; for(int i=0;i<m;i++){ int p;cin>>p>>C; p--; pair<int,int> ff=edgeset[2*p]; pair<int,int> ss=edgeset[2*p+1]; side[ff.first][ff.second].second++; side[ss.first][ss.second].second++; } for(int i=1;i<20;i++) father[1][i] ={1,0}; dfs(1); for(int j=1;j<20;j++){ for(int i=2;i<=n;i++){ int v = father[i][j-1].second+father[father[i][j-1].first][j-1].second; father[i][j] = {father[father[i][j-1].first][j-1].first,v}; } } while(q--){ int a,b,x,y;cin>>a>>b>>x>>y; int cnt = get(a,b); int c = y/C; int howmany = max(0,cnt-c); cout<<x-howmany<<"\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...