| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 888622 | vjudge1 | Two Currencies (JOI23_currencies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update> ordered_set;
const int mod= 1e9 +7;
const int N = 1e5 + 6;
int n, q, timer, m;
int tin[N], tout[N],cnt[N],prad[N];
map<pii,int>mp;
map<pii,vector<int>>cost;
int up[20][N];
vector <int> g[N];
//------------------lca--------------------
void dfs(int v, int pr) {
tin[v] = ++timer;
up[0][v] = pr;
for (int i = 1; i <= 17; i++) {
up[i][v] = up[i - 1][ up[i - 1][v] ];
}
for (int to : g[v]) {
if (to == pr) continue;
dfs(to, v);
}
tout[v] = timer;
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 17; i >= 0; i--) {
if (!upper(up[i][a], b)) {
a = up[i][a];
}
}
return up[0][a];
}
//-------------------cnt of marked--------------
void mark(int x,int pr){
for(auto to:g[x]){
if(to==pr)continue;
cnt[to] = cnt[x];
cnt[to] += mp[{x,to}];
mark(to,x);
}
}
//-------------------------kolhoz-----------
void dfs1(int x,int pr){
for(auto to:g[x]){
// cout<<to<<" ";
if(to==pr)continue;
prad[to] = x;
dfs1(to,x);
}
}
void solve(){
cin >> n >> m >> q;
vector<pii>v;
for (int i = 1; i < n; i++) {
int u, o;
cin >> u >> o;
g[u].push_back(o);
g[o].push_back(u);
v.pb({u,o});
}
int val = 0;
map<int,int>mps;
bool flag = false;
for(int i = 0; i < m; i++){
int j,k;
cin>>j>>k;
pii l = v[j-1];
mp[{l.f,l.s}]++;
mp[{l.s,l.f}]++;
cost[{l.f,l.s}].pb(k);
cost[{l.s,l.f}].pb(k);
val = k;
mps[k]++;
if(mps[k]==1&&i>0)flag = true;
}
if(!flag){
////----------------------28---------------------
dfs(1, 1);
mark(1,-1);
while (q--) {
int u, v;
int sum,gold;
cin >> u >> v >> gold >> sum;
int h = lca(u, v);
int ans = cnt[u] + cnt[v];
ans -= cnt[h] * 2;
int l = 1,r = ans,ans1 = 0;
while(l<=r){
int mid = (l+r)/2;
if(mid*val>sum){
r = mid - 1;
}
else {
ans1 = mid;
l = mid + 1;
}
}
ans -= ans1;
if(gold-ans<0)cout<<-1<<"\n";
else cout<<gold - ans<<"\n";
}
}
else{
//-----------------------------10-----------------------------
while(q--){
int a,b,c,d;
cin>>a>>b>>c>>d;
dfs1(a,-1);
vector<int>ans;
while(b!=a){
for(auto to:cost[{b,prad[b]}])ans.pb(to);
b = prad[b];
}
sort(all(ans));
for(int i = 0;i<ans.size();i++){
if(d - ans[i]<0){
int u = ans.size() - i;
c = max(c - u, 0ll-1ll);
break;
}
d -= ans[i];
}
cout<<c<<"\n";
}
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int tt = 1;
while(tt--){
solve();
}
}