Submission #1086579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086579		nathan4690	Two Currencies (JOI23_currencies)	C++17	100 / 100	548 ms	54568 KiB

currencies

// The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
// Spring Training/Qualifying Trial
// March 18–22, 2023 (Komaba, Tokyo)
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 4e5+5, inf=1e18;

struct FenwickTree{
    int n;
    vector<long long> bit;
    FenwickTree(){}
    FenwickTree(int n): n(n), bit(n+1, 0LL){}
    void update(int idx, long long v){
        if(idx <= 0) return;
        for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
    }
    long long getSum(int idx){
        if(idx <= 0) return 0;
        long long res = 0;
        for(;idx;idx-=idx&-idx) res += bit[idx];
        return res;
    }
};

struct Query{
    int s, t, x, y, lc, l, r, mid, idx;
    bool operator<(const Query &rhs) const{
        return mid < rhs.mid;
    }
};

struct Edge{
    int u, v, w;
    Edge(){};
    Edge(int u, int v, int w): u(u), v(v), w(w){};
    bool operator<(const Edge &rhs) const{
        return w > rhs.w;
    }
    bool operator>(const Edge &rhs) const{
        return w < rhs.w;
    }
};

int n,m,q,depth[maxn],ans[maxn];
int up[18][maxn];
vector<int> G[maxn];
Edge edges[maxn],ee[maxn];
FenwickTree fen,bit;
Query qu[maxn];

void binlift(int u, int p){
    up[0][u] = p;
    for(int i=1;i<18;i++){
        up[i][u] = up[i-1][up[i-1][u]];
    }
    for(int c: G[u]){
        if(c != p){
            depth[c] = depth[u] + 1;
            binlift(c, u);
        }
    }
}

void jump(int& u, int len){
    for(int i=0;i<18;i++){
        if(len & (1 << i)) u = up[i][u];
    }
}

int LCA(int u, int v){
    if(depth[u] > depth[v]) swap(u, v);
    jump(v, depth[v] - depth[u]);
    if(u == v) return u;
    for(int i=17;i>=0;i--){
        if(up[i][u] != up[i][v]){
            u = up[i][u];
            v = up[i][v];
        }
    }
    return up[0][u];
}

int sp[maxn],ep[maxn],timer;
void tour(int u, int p){
    sp[u] = timer++;
    for(int c: G[u]){
        if(c != p) tour(c, u);
    }
    ep[u] = timer;
}

ll V(int u){
    return fen.getSum(sp[u]);
}
ll V2(int u){
    return bit.getSum(sp[u]);
}

void check(int i, int &ptr){
    while(qu[ptr].mid == i){
        if(qu[ptr].l > qu[ptr].r){
            ptr++;
            continue;
        }
        ll sum = 1LL * V(qu[ptr].s) + V(qu[ptr].t) - 2*V(qu[ptr].lc);
        // cout << i << ' ' << qu[ptr].s << ' ' << qu[ptr].t << ' ' << sum;el;
        if(sum <= qu[ptr].y) qu[ptr].l = qu[ptr].mid + 1;
        else qu[ptr].r = qu[ptr].mid - 1;
        qu[ptr].mid = (qu[ptr].l + qu[ptr].r) / 2;
        ptr++;
    }
}

bool cmp(Query x, Query y){
    return x.r < y.r;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> m >> q;
    fen = FenwickTree(n);
    f1(i,n-1){
        int u, v; cin >> u >> v;
        ee[i] = Edge(u, v, 0);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    depth[1] = 1;
    binlift(1, 0);
    timer = 1;
    tour(1, 0);
    int ttt = 0;
    f1(i,m){
        int p, c; cin >> p >> c;
        edges[i] = ee[p];
        edges[i].w = c;
        if(depth[edges[i].u] < depth[edges[i].v]) swap(edges[i].u, edges[i].v);
        // cout << edges[i].u << ' ' << edges[i].v << ' ' << depth[edges[i].u] << " ?? " << depth[edges[i].v];el;
    }
    // sort(edges+1,edges+n);
    sort(edges+1,edges+m+1,greater<Edge>());
//    f1(i,m){
//        cout << edges[i].u << " -> " << edges[i].v << " w = " << edges[i].w;el;
//    }
    f1(i,q){
        cin >> qu[i].s >> qu[i].t >> qu[i].x >> qu[i].y;
        qu[i].idx = i;
        qu[i].lc = LCA(qu[i].s, qu[i].t);
        qu[i].l = 0; qu[i].r = m;
    }
    qu[q+1].mid = 2e9;
    f1(_,30){
        f1(i,q) qu[i].mid = (qu[i].l + qu[i].r) / 2;
        sort(qu+1,qu+q+1);
        fen = FenwickTree(n + 1);
        int ptr = 1;
        ll sum = 0;
        // v is the parent of u
        f1(i,m){
            check(i-1, ptr);
            fen.update(sp[edges[i].u], edges[i].w);
            fen.update(ep[edges[i].u], -edges[i].w);
            // cout << edges[i].u << " -> " << edges[i].v;el;
        }
        check(m, ptr);
    }
    bit = FenwickTree(n+1);
    sort(qu+1,qu+q+1,cmp);
    int ptr = q;
    for(int i=m;i>=1;i--){
        while(qu[ptr].r == i){
            ll sum = V2(qu[ptr].s) + V2(qu[ptr].t) - 2*V2(qu[ptr].lc);
            // cout << qu[ptr].idx << ' ' << qu[ptr].r <<
            ans[qu[ptr].idx] = qu[ptr].x - sum;
            ptr--;
        }
        bit.update(sp[edges[i].u], 1);
        bit.update(ep[edges[i].u], -1);
    }
    qu[0].r = -1;
    while(qu[ptr].r == 0){
        ll sum = V2(qu[ptr].s) + V2(qu[ptr].t) - 2*V2(qu[ptr].lc);
        // cout << qu[ptr].idx << ' ' << qu[ptr].r <<
        ans[qu[ptr].idx] = qu[ptr].x - sum;
        ptr--;
    }
    f1(i,q) cout << (ans[i] >= 0 ? ans[i] : -1) << '\n';
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:169:12: warning: unused variable 'sum' [-Wunused-variable]
  169 |         ll sum = 0;
      |            ^~~
currencies.cpp:144:9: warning: unused variable 'ttt' [-Wunused-variable]
  144 |     int ttt = 0;
      |         ^~~
currencies.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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