Submission #1009685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009685		NintsiChkhaidze	Two Currencies (JOI23_currencies)	C++17	100 / 100	2525 ms	63436 KiB

currencies

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;
 
const int N = 1e5 + 3,inf = 1e18;
int A[N],B[N],dep[N],d[25][N];
int L[N],R[N],S[N],T[N],X[N],Y[N],C[N],ans[N],total[N];
int timer,tin[N],tout[N],t[7][4*N],val[N];
vector <int> v[N];

void dfs(int x,int par){
    d[0][x] = par;
    tin[x] = ++timer;
    dep[x] = dep[par] + 1;

    for (int to: v[x]){
        if (to != par) dfs(to,x);
    }

    tout[x] = timer;
}

int lca(int x,int y){
    if (dep[x] < dep[y]) swap(x,y);
    for (int i = 20; i >= 0; i--)
        if (dep[d[i][x]] >= dep[y]) x= d[i][x];

    if (x==y) return x;

    for (int i=20;i>=0;i--)
        if (d[i][x] != d[i][y]) {
            x = d[i][x];
            y = d[i][y];
        }
    return d[0][x];
}

void upd(int id,int h,int l,int r,int L,int R,int val){
    if (r < L || R < l) return;
    if (L <= l && r <= R){
        t[id][h] += val;
        return;
    }

    upd(id,left,L,R,val);
    upd(id,right,L,R,val);
}

int get(int id,int h,int l,int r,int idx){
    if (l == r) return t[id][h];
    if (idx > (l + r)/2) return t[id][h] + get(id,right,idx);
    return t[id][h] + get(id,left,idx);
}

void clear(int h,int l,int r){
    t[1][h] = t[2][h] = 0;
    if (l == r) return;
    clear(left);
    clear(right);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
 
    int n,m,q;
    cin>>n>>m>>q;

    for (int i = 1; i < n; i++){
        cin >> A[i] >> B[i];
        v[A[i]].pb(B[i]);
        v[B[i]].pb(A[i]);
    }

    dfs(1,1);
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++)
            d[j][i] = d[j - 1][d[j - 1][i]];
        
    vector <pii> vec;
    for (int i = 1; i <= m; i++){
        int x,y;
        cin>>x>>y;
        vec.pb({y,x});
    }
    sort(vec.begin(),vec.end());

    for (int i= 1; i < n; i++){
        if (dep[A[i]] > dep[B[i]]) swap(A[i],B[i]);
    }

    for (int i = 0;i < vec.size(); i++){
        int x = B[vec[i].s];
        upd(3,1,1,n,tin[x],tout[x],+1);
    }

    for (int i = 1; i <= q; i++){
        cin>>S[i]>>T[i]>>X[i]>>Y[i];
        L[i] = 0;
        R[i] = vec.size() - 1;
        C[i] = lca(S[i],T[i]);
        total[i] = get(3,1,1,n,tin[S[i]]) + get(3,1,1,n,tin[T[i]]) - 2*get(3,1,1,n,tin[C[i]]);
    }

    for (int j = 1; j <= 30; j++){
        clear(1,1,n);

        vector <pii> qr;
        for (int i = 1; i <= q; i++){
            int mid = (L[i] + R[i])/2;
            qr.pb({mid,i});
        }
        sort(qr.begin(),qr.end());

        int l = 0;
        for (int i = 0; i < qr.size(); i++){
            int id = qr[i].s,mid = qr[i].f;
            while (l <= mid){
                int x = B[vec[l].s];
                upd(1,1,1,n,tin[x],tout[x],vec[l].f);
                upd(2,1,1,n,tin[x],tout[x],1);
                ++l;
            }

            int sum = get(1,1,1,n,tin[S[id]]) + get(1,1,1,n,tin[T[id]]) - 2*get(1,1,1,n,tin[C[id]]);
            if (sum <= Y[id]){
                int cnt = get(2,1,1,n,tin[S[id]]) + get(2,1,1,n,tin[T[id]]) - 2*get(2,1,1,n,tin[C[id]]);
                ans[id] = cnt;
                L[id] = mid + 1;
            }else{
                R[id] = mid - 1;
            }   
        }
    }

    for (int i = 1; i <= q; i++){
        ans[i] = total[i] - ans[i];
        
        if (ans[i] <= X[i]) cout<<X[i] - ans[i]<<endl;
        else cout<<-1<<endl;
    }

}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:98:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 0;i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
currencies.cpp:122:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (int i = 0; i < qr.size(); i++){
      |                         ~~^~~~~~~~~~~

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