Submission #1032267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032267		Andrey	Two Currencies (JOI23_currencies)	C++14	100 / 100	2329 ms	105108 KiB

currencies

#include<bits/stdc++.h>
using namespace std;

vector<pair<long long,long long>> haha[100001];
vector<long long> edge[100001];
vector<pair<long long,long long>> wut(1,{-LLONG_MAX,0});
vector<long long> pos(100001);
vector<long long> st(100001);
vector<long long> br(100001);
long long bruh[100001][17];
vector<pair<long long,pair<long long,long long>>> idk[100010];
vector<long long> dep(100001);
long long z = 1;

pair<long long,long long> dude(long long x, long long t) {
    long long l = 0,r = idk[x].size()-1;
    while(l < r) {
        long long mid = (l+r+1)/2;
        if(idk[x][mid].first > t) {
            r = mid-1;
        }
        else {
            l = mid;
        }
    }
    return idk[x][l].second;
}

pair<long long,long long> no(long long r, long long t) {
    long long c = 0,a = 0,b = 0;
    for(long long i = 17; i >= 0; i--) {
        if(c+(1 << i) <= r) {
            c+=(1 << i);
            pair<long long,long long> d = dude(c,t);
            a+=d.first;
            b+=d.second;
        }
    }
    return {a,b};
}

void upd(long long a, long long x, long long t) {
    long long q = 1;
    if(x < 0) {
        q = -1;
    }
    while(a < 100001) {
        pair<long long,long long> c = idk[a][idk[a].size()-1].second;
        idk[a].push_back({t,{c.first+x,c.second+q}});
        a+=((a)&(-a));
    }
}

void dfs(long long a, long long t, long long d) {
    dep[a] = d;
    st[a] = 1;
    pos[a] = z;
    bruh[a][0] = t;
    z++;
    for(pair<long long,long long> v: haha[a]) {
        if(v.first != t) {
            br[v.first]+=br[a];
            for(long long x = 0; x < edge[v.second].size(); x++) {
                wut.push_back({edge[v.second][x],v.first});
                br[v.first]++;
            }
            dfs(v.first,a,d+1);
            st[a]+=st[v.first];
        }
    }
}

long long lca(long long a, long long b) {
    if(dep[a] < dep[b]) {
        swap(a,b);
    }
    long long c = dep[a]-dep[b];
    for(long long i = 0; i < 17; i++) {
        if((1 << i)&c) {
            a = bruh[a][i];
        }
    }
    if(a == b) {
        return a;
    }
    for(long long i = 16; i >= 0; i--) {
        if(bruh[a][i] != bruh[b][i]) {
            a = bruh[a][i];
            b = bruh[b][i];
        }
    }
    return bruh[a][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n,m,q,a,b,x,y;
    cin >> n >> m >> q;
    for(long long i = 1; i <= n-1; i++) {
        cin >> a >> b;
        haha[a].push_back({b,i});
        haha[b].push_back({a,i});
    }
    for(long long i = 0; i < m; i++) {
        cin >> a >> b;
        edge[a].push_back(b);
    }
    dfs(1,-1,1);
    for(long long i = 1; i < 17; i++) {
        for(long long j = 1; j <= n; j++) {
            if(bruh[j][i-1] == -1) {
                bruh[j][i] = -1;
            }
            else {
                bruh[j][i] = bruh[bruh[j][i-1]][i-1];
            }
        }
    }
    sort(wut.begin(),wut.end());
    for(long long i = 1; i <= 100009; i++) {
        idk[i].push_back({0,{0,0}});
    }
    for(long long i = 1; i < wut.size(); i++) {
        long long a = wut[i].second,b = wut[i].first;
        long long z = a;
        a = pos[a];
        upd(a,b,i);
        upd(a+st[z],-b,i);
    }
    for(long long i = 0; i < q; i++) {
        cin >> a >> b >> x >> y;
        long long c = lca(a,b);
        long long d = br[a]+br[b]-2*br[c];
        a = pos[a];
        b = pos[b];
        c = pos[c];
        long long l = 0,r = wut.size()-1;
        while(l < r) {
            long long mid = (l+r+1)/2;
            if(no(a,mid).first+no(b,mid).first-2*no(c,mid).first <= y) {
                l = mid;
            }
            else {
                r = mid-1;
            }
        }
        cout << max(-1LL,x+(no(a,l).second+no(b,l).second-2*no(c,l).second)-d) << "\n";
    }
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(long long int, long long int, long long int)':
currencies.cpp:63:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             for(long long x = 0; x < edge[v.second].size(); x++) {
      |                                  ~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:126:28: 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]
  126 |     for(long long i = 1; i < wut.size(); i++) {
      |                          ~~^~~~~~~~~~~~

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