Submission #888804

#	Time	Username	Problem	Language	Result	Execution time	Memory
888804		vjudge1	Two Currencies (JOI23_currencies)	C++17	10 / 100	5073 ms	40764 KiB

currencies

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 1e5+50;
vi g[N];
map<pii, vi> mp;
map<pii, int> mp2;
int pre[N];
int n, q, timer;
int tin[N], tout[N];
int up[20][N];
int num[N]{};

void dfs(int v, int pr) {
    tin[v] = ++timer;
    up[0][v] = pr;
    for (int i = 1; i <= 19; 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 = 19; i >= 0; i--) {
        if (!upper(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];
}

void sukfe(int v, int pr){
    for (int to : g[v]) {
        if (to == pr) continue;
        num[to] = num[v];
        num[to] += mp2[{v, to}];
        dfs(to, v);
    }
}
void dfs2(int v, int pr){
    for (int to : g[v]) {
        if (to == pr) continue;
        pre[to] = v;
        dfs2(to, v);
    }
}
map<int,int> muka;
void solve(){
  int n, m, q;
  cin >> n >> m >> q;
  vii cui;
  for(int i = 0; i < n-1; i++){
    int a, b;
    cin >> a >> b;
    g[a].pb(b);
    g[b].pb(a);
    cui.pb({a, b});
  }
  bool f = 1;
  int c, j;
  for(int i = 0; i < m; i++){
    cin >> j >> c;
    j--;
    pii kio = cui[j];
    mp[{kio.ff, kio.ss}].pb(c);
    mp[{kio.ss, kio.ff}].pb(c);
    mp2[{kio.ff, kio.ss}]++;
    mp2[{kio.ss, kio.ff}]++;
    if(muka[c]!=1&&i>0)f=0;
  }
  if(f){
    dfs(1, -1);
    sukfe(1, -1);
    while(q--){
      int a, b, x, y;
      cin >> a >> b >> x >> y;
      int cnt = num[a] + num[b];
      int lc = lca(a, b);
      cnt -= num[lc] * 2;
      int l = 1, r = cnt, ans = 0;
      while(l <= r){
        int m = (l+r)>>1;
        if(m*c>y)r = m-1;
        else{
          ans = m;
          l = m+1;
        }
      }
      cnt -= ans;
      if(x - cnt < 0)cout << -1 << '\n';
      else cout << x - cnt << '\n';
    }
  }else{
    vi pas;
    while(q--){
      int s, t, x, y;
      cin >> s >> t >> x >> y;
      dfs2(s, -1);
      int r = t;
      while(r!=s){
        for(auto i:mp[{r, pre[r]}])pas.pb(i);
        r = pre[r];
      }
      sort(all(pas));
      for(auto i:pas){
        if(i <= y)y -= i;
        else x--;
      }pas.clear();
      cout << (x < 0 ? -1 : x) << '\n';
    }
  }
  
}
main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t = 1;
  //~ cin >> t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

currencies.cpp:139:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  139 | main(){
      | ^~~~

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