Submission #1269767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269767		huudai	Two Currencies (JOI23_currencies)	C++20	100 / 100	760 ms	43384 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back

#define BIT(x,i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))  

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

#define file "task"

const int maxn = 1e5 + 5;
const int MOD  = 1e9 + 7;
const int oo   = 1e9;
const ll  OO   = 1e18;
const int LOG  = 19;

int n, m, q;
int timeDfs;
int l[maxn];
int r[maxn];
int h[maxn];
int f[maxn];
pii p[maxn];
int st[maxn];
int en[maxn];
int ans[maxn];
int up[maxn][LOG + 2];
pii edge[maxn];
int check[maxn];
vector<pii> g[maxn];
vector<int> tmp[maxn];

struct fenwick{
    ll fw[maxn];
    fenwick(){
        memset(fw, 0, sizeof(fw));
    }

    void update(int id, int val){
        for(;id <= n; id += id & -id) fw[id] += val;
    }

    void update(int l, int r, int val){
        update(l, val);
        update(r + 1, -val);
    }

    ll get(int id){
        ll ret = 0;
        for(;id > 0; id -= id & -id) ret += fw[id];
        return ret;
    }
} bit1, bit2;

struct item{
    int u, v, ancestor;
    ll gold, silver;
    item(){}
    item(int u, int v, int ancestor, ll gold, ll silver) :
        u(u), v(v), ancestor(ancestor), gold(gold), silver(silver){}
} query[maxn];

void input(){
    cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        g[u].pb(mp(v, i));
        g[v].pb(mp(u, i));
        edge[i] = mp(u, v);
    }
    for(int i = 1; i <= m; i++){
        int id, w; cin >> id >> w;
        check[id]++;
        p[i] = mp(w, id);
    }
}

void dfs(int u, int dad){
    st[u] = ++timeDfs;
    for(auto [v, id] : g[u]){
        if(v == dad) continue;
        h[v] = h[u] + 1;
        f[v] = f[u] + check[id];
        up[v][0] = u;
        for(int i = 1; i <= LOG; i++)
            up[v][i] = up[up[v][i - 1]][i - 1];
        dfs(v, u);
    }
    en[u] = timeDfs;
}

int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    for(int i = LOG; i >= 0; i--)
        if(h[u] - MASK(i) >= h[v])
            u = up[u][i];
    if(u == v) return u;

    for(int i = LOG; i >= 0; i--)
        if(up[u][i] != up[v][i])
            u = up[u][i], v = up[v][i];
    return up[u][0];
}
void proc(){
    dfs(1, 1);

    sort(p + 1, p + 1 + m);
    for(int i = 1; i <= q; i++){
        int u, v; ll gold, silver;
        cin >> u >> v >> gold >> silver;
        query[i] = item(u, v, lca(u, v), gold, silver);
        l[i] = 1; r[i] = m;
    }

    for(int i = 1; i <= m; i++){
        auto [w, id] = p[i];
        auto &[u, v] = edge[id];
        if(h[u] > h[v]) swap(u, v); 
    }

    while(1){
        bool ok = 1;
        for(int i = 1; i <= q; i++){
            if(l[i] > r[i]) continue;
            int mid = (l[i] + r[i]) / 2;
            tmp[mid].pb(i);
            ok = 0;
        }

        if(ok) break;
        
        bit1 = bit2 = fenwick();
        for(int i = 1; i <= m; i++){
            auto [w, id] = p[i];
            auto [u, v] = edge[id];

            bit1.update(st[v], en[v], w);
            bit2.update(st[v], en[v], 1);

            for(int idx : tmp[i]){
                auto [u, v, ancestor, gold, silver] = query[idx];
                ll sum = bit1.get(st[u]) + bit1.get(st[v]) - 2LL * bit1.get(st[ancestor]);
                if(sum <= silver){
                    l[idx] = i + 1;
                    ans[idx] = bit2.get(st[u]) + bit2.get(st[v]) - 2LL * bit2.get(st[ancestor]);
                } else {
                    r[idx] = i - 1;
                }
            }

            tmp[i].clear();
        }
    }

    for(int i = 1; i <= q; i++){
        auto [u, v, ancestor, gold, silver] = query[i];
        int sum = f[u] + f[v] - 2 * f[lca(u, v)];
        if(gold >= sum - ans[i]){
            cout << gold - (sum - ans[i]) << '\n';
        } else {
            cout << -1 << '\n';
        }
    }

}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0); cout.tie(nullptr);    
    if(fopen(file".inp", "r")){
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }
    
    input();
    proc();

    return 0;
}

Compilation message (stderr)

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

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