Submission #1253263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253263		Peter2017	Two Currencies (JOI23_currencies)	C++20	100 / 100	2606 ms	65888 KiB

currencies

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pill pair<int,ll>
#define mem(a, b) memset(a, b, sizeof(a))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define int ll
#define name "test"

using namespace std;

const int N = 2e5 + 5;
const int LOG = 31 - __builtin_clz(N);

template <typename T1, typename T2> bool maxi(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <typename T1, typename T2> bool mini(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}

struct item
{
    int u, v, gold_coin;
    long long silver_coin;
    void input(){
        cin >> u >> v >> gold_coin >> silver_coin;
    }
};

struct FenwickTree{
    int n;
    int cnt[N];
    long long val[N];

    FenwickTree(){}

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

    void update(int idx, int x){
        assert(idx > 0);
        for (; idx <= n; idx += idx & -idx){
            val[idx] += x;
            cnt[idx] += (x < 0 ? -1 : 1);
        }
    }

    pair<long long, int> get(int idx){
        int s_cnt = 0;
        long long sum = 0;
        for (; idx; idx -= idx & -idx){
            sum += val[idx];
            s_cnt += cnt[idx];
        }
        return {sum, s_cnt};
    }
} ft;

int n;
int m;
int q;
int st[N];
int ed[N];
int rep[N];
int ans[N];
int L[N], R[N];
int high[N];
int par[N][LOG + 1];
item query[N];
pii edges[N];
pii checkpoint[N];
vector<int> adj[N];
vector<int> query_list[N];

void load(){
    cin.tie(0)->sync_with_stdio(0);
    if (fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void input(){
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(i);
        adj[v].push_back(i);
        edges[i] = {u, v};
    }
    for (int i = 1; i <= m; i++){
        cin >> checkpoint[i].fi >> checkpoint[i].se;
    }
    for (int i = 1; i <= q; i++){
        query[i].input();
        L[i] = 0; 
        R[i] = m;
    }
}

void dfs_euler(int u, int pre){
    static int cntDfs = 0;
    st[u] = ++cntDfs;
    for (int idx : adj[u]){
        int v = edges[idx].fi + edges[idx].se - u;
        if (v != pre){
            rep[idx] = v;
            par[v][0] = u;
            high[v] = high[u] + 1;
            dfs_euler(v, u);
        }
    }
    ed[u] = cntDfs;
}

bool cmp(pii x, pii y){
    return x.se < y.se;
}

int LCA(int u, int v){
    if (high[u] < high[v]) swap(u, v);
    for (int j = LOG; j >= 0; j--) if (high[par[u][j]] >= high[v]) u = par[u][j];
    if (u == v) return u;
    for (int j = LOG; j >= 0; j--) if (par[u][j] != par[v][j]){
        u = par[u][j];
        v = par[v][j];
    }
    return par[u][0];
}

void solve(){
    mem(ans, -1);
    dfs_euler(1, 0);
    sort(checkpoint + 1, checkpoint + m + 1, cmp);

    for (int j = 1; j <= LOG; j++)
        for (int i = 1; i <= n; i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    high[0] = -1;

    ft.n = n;
    bool processing = 1;
    while (processing){
        processing = 0;
        for (int i = 1; i <= q; i++){
            if (L[i] <= R[i]){
                processing = 1;
                int m = (L[i] + R[i]) / 2;
                query_list[m].push_back(i);
            }
        }
        ft.reset();
        for (int i = 0; i <= m; i++){
            if (i && checkpoint[i].se <= (int)1e9){
                ft.update(st[rep[checkpoint[i].fi]], checkpoint[i].se);
                ft.update(ed[rep[checkpoint[i].fi]] + 1, -checkpoint[i].se);
            }
            for (int j : query_list[i]){
                auto [u, v, gold_coin, silver_coin] = query[j];
                int ancestor = LCA(u, v);
                pair<long long, int> tmp1 = ft.get(st[u]);
                pair<long long, int> tmp2 = ft.get(st[v]);
                pair<long long, int> tmp3 = ft.get(st[ancestor]);
                if (tmp1.fi + tmp2.fi - tmp3.fi * 2 <= silver_coin){
                    ans[j] = tmp1.se + tmp2.se - tmp3.se * 2;
                    L[j] = i + 1;
                } else R[j] = i - 1;
            }
            query_list[i].clear();
        }
    }
    ft.reset();
    for (int i = 1; i <= m; i++){
        ft.update(st[rep[checkpoint[i].fi]], checkpoint[i].se);
        ft.update(ed[rep[checkpoint[i].fi]] + 1, -checkpoint[i].se);
    }
    for (int i = 1; i <= q; i++){
        if (ans[i] == -1) cout << -1 << '\n';
        else {
            auto [u, v, gold_coin, silver_coin] = query[i];
            int ancestor = LCA(u, v);
            pair<long long, int> tmp1 = ft.get(st[u]);
            pair<long long, int> tmp2 = ft.get(st[v]);
            pair<long long, int> tmp3 = ft.get(st[ancestor]);
            int tmp = tmp1.se + tmp2.se - tmp3.se * 2 - ans[i];
            if (tmp <= gold_coin) cout << gold_coin - tmp << '\n';
            else cout << -1 << '\n';
        }
    }
}

signed main(){
    load();
    input();
    solve();
}

Compilation message (stderr)

currencies.cpp: In function 'void load()':
currencies.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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