Submission #1009676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009676		NintsiChkhaidze	Two Currencies (JOI23_currencies)	C++17	0 / 100	2 ms	10844 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 timer,tin[N],tout[N],t[7][4*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 get(id,right,idx);
    return 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);
    }

    //neli
    for (int i = 1; i <= q; i++){
        int s,t,x,y;
        cin>>s>>t>>x>>y;

        int c = lca(s,t);
        int total = get(3,1,1,n,tin[s]) + get(3,1,1,n,tin[t]) - 2*get(3,1,1,n,tin[c]);
        int ans = total;
        
        clear(1,1,n);
        for (int j = 0; j < vec.size(); j++){
            int x = B[vec[j].s];
            upd(1,1,1,n,tin[x],tout[x],vec[j].f);
            upd(2,1,1,n,tin[x],tout[x],1);

            int sum = get(1,1,1,n,tin[s]) + get(1,1,1,n,tin[t]) - 2*get(1,1,1,n,tin[c]);
            if (sum <= y){
                int cnt = get(2,1,1,n,tin[s]) + get(2,1,1,n,tin[t]) - 2*get(2,1,1,n,tin[c]);
                ans = total - cnt;
            }else{
                break;
            }
        }

        if (ans <= x) cout<<x - ans<<endl;
        else cout<<-1<<endl;
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:97: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]
   97 |     for (int i = 0;i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
currencies.cpp:112: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]
  112 |         for (int j = 0; j < vec.size(); j++){
      |                         ~~^~~~~~~~~~~~

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