Submission #1296031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296031		fuyu	Two Currencies (JOI23_currencies)	C++20	100 / 100	1406 ms	32896 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ins insert
#define fi first
#define se second
#define ld long double
#define ALL(x) (x).begin(), (x).end()
#define MASK(x) (1ULL << (x))
#define BIT(x, k) ((x) >> (k) & 1)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)

template<typename T1, typename T2> bool maximize(T1 &x, const T2 &y){
    if (x < y){
        x = y;
        return 1;
    }
    return 0;
}

template<typename T1, typename T2> bool minimize(T1 &x, const T2 &y){
    if (x > y){
        x = y;
        return 1;
    }
    return 0;
}

bool ST_ALLOC;

#define file "CODE"

void fastio(){
    if (fopen(file".INP", "r")){
        freopen(file".INP", "r", stdin);
        freopen(file".OUT", "w", stdout);
    }
}

const int maxn = 1e5 + 9;

struct Station{
    int u, cost;

    friend istream &operator >> (istream &inp, Station &s){
        inp >> s.u >> s.cost;
        return inp;
    }
};

bool cmpStation(const Station &a, const Station &b){
    return a.cost < b.cost;
}

struct Query{
    int u, v;
    ll gc, sc;

    friend istream &operator >> (istream &inp, Query &q){
        inp >> q.u >> q.v >> q.gc >> q.sc;
        return inp;
    }
};

struct Node{
    int top, id;
};

int n, m, t, timer;
int sz[maxn];
int st[maxn];
int par[maxn];
int head[maxn];
int L[maxn];
int R[maxn];
int ans[maxn];
int belong[maxn];
ll gol[maxn];
ll sil[maxn];
Query q[maxn];
Station a[maxn];
vector<Node> adj[maxn];
vector<int> event[maxn];

void build(int u, int pre){
    sz[u] = 1;

    for(auto e : adj[u]){
        int v = e.top, id = e.id;

        if (v == pre)
            continue;

        belong[id] = v;

        build(v, u);

        sz[u] += sz[v];
    }
}

void hld(int u, int pre, int headNode){
    st[u] = ++timer;
    head[u] = headNode;

    int bigChild = -1;

    for(auto e : adj[u]){
        int v = e.top;

        if (v == pre)
            continue;

        par[v] = u;

        if (bigChild == -1)
            bigChild = v;

        if (sz[bigChild] < sz[v])
            bigChild = v;
    }

    if (bigChild != -1)
        hld(bigChild, u, headNode);

    for(auto e : adj[u]){
        int v = e.top;

        if (v == pre || v == bigChild)
            continue;

        hld(v, u, v);
    }
}

void upd(ll bit[], int pos, int val){
    if (pos <= 0)
        return;

    for(; pos <= n; pos += (pos & (-pos)))
        bit[pos] += val;
}

ll get(ll bit[], int pos){
    ll res = 0;

    for(; pos > 0; pos -= (pos & (-pos)))
        res += bit[pos];

    return res;
}

ll getRange(ll bit[], int l, int r){
    maximize(l, 1);

    if (l > r)
        return 0;

    return get(bit, r) - get(bit, l - 1);
}

void reset(){
    for(int i = 1; i <= n; ++i)
        gol[i] = sil[i] = 0;
}

int getGold(int u, int v){
    int res = 0;

    for(; head[u] != head[v]; u = par[head[u]]){
        if (st[u] < st[v])
            swap(u, v);

        res += getRange(gol, st[head[u]], st[u]);
    }

    if (u != v){
        if (st[u] > st[v])
            swap(u, v);

        res += getRange(gol, st[u] + 1, st[v]);
    }

    return res;
}

ll getSil(int u, int v){
    ll res = 0;

    for(; head[u] != head[v]; u = par[head[u]]){
        if (st[u] < st[v])
            swap(u, v);

        res += getRange(sil, st[head[u]], st[u]);
    }

    if (u != v){
        if (st[u] > st[v])
            swap(u, v);

        res += getRange(sil, st[u] + 1, st[v]);
    }

    return res;
}

bool EN_ALLOC;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    fastio();

    cin >> n >> m >> t;

    for(int i = 1; i <= n - 1; ++i){
        int u, v; cin >> u >> v;

        adj[u].pb({v, i});
        adj[v].pb({u, i});
    }

    for(int i = 1; i <= m; ++i)
        cin >> a[i];

    for(int i = 1; i <= t; ++i)
        cin >> q[i];

    build(1, 1);

    for(int i = 1; i <= m; ++i)
        a[i].u = belong[a[i].u];

    sort(a + 1, a + m + 1, cmpStation);

    hld(1, 1, 1);

    memset(ans, -1, sizeof(ans));

    for(int i = 1; i <= t; ++i)
        L[i] = 0, R[i] = m;

    bool parallel = 1;

    while (parallel){
        parallel = 0;

        for(int i = 1; i <= t; ++i){
            if (L[i] > R[i])
                continue;

            int mid = L[i] + R[i] >> 1;

            event[mid].pb(i);
        
            parallel = 1;
        }

        if (!parallel)
            break;

        reset();

        for(int i = 1; i <= m; ++i){
            int u = a[i].u;

            upd(gol, st[u], 1);
        }

        for(int mid = 0; mid <= m; ++mid){
            if (mid){
                int node = a[mid].u, cost = a[mid].cost;

                upd(gol, st[node], -1);
                upd(sil, st[node], cost);
            }

            for(int idx : event[mid]){
                int u = q[idx].u, v = q[idx].v;
                ll gc = q[idx].gc, sc = q[idx].sc;

                int ng = getGold(u, v);
                ll ns = getSil(u, v);

                if (ng <= gc && ns <= sc)
                    maximize(ans[idx], gc - ng);

                if (ng <= gc && ns <= sc)
                    L[idx] = mid + 1;
                else if (ng <= gc && ns > sc)
                    R[idx] = mid - 1;
                else if (ng > gc && ns <= sc)
                    L[idx] = mid + 1;
                else
                    R[idx] = mid - 1;
            }

            if (event[mid].size())
                event[mid].clear();
        }
    }

    for(int i = 1; i <= t; ++i)
        cout << ans[i] << '\n';

    cerr << "Time ran : " << TIME << "s\n";
    cerr << "Static memory used : " << fixed << setprecision(2) << (((&EN_ALLOC) - (&ST_ALLOC)) / (1.0l * 1024 * 1024)) << "mb\n";
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void fastio()':
currencies.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(file".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(file".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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