Submission #737717

#	Time	Username	Problem	Language	Result	Execution time	Memory
737717		Username4132	Two Currencies (JOI23_currencies)	C++14	100 / 100	3325 ms	202716 KiB

currencies

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
using pli=pair<ll, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
#define F first
#define S second

inline pli add(pli p1, pli p2){
    return {p1.F+p2.F, p1.S+p2.S};
}

struct Vertex{
    pli sum;
    Vertex *l, *r;
    Vertex(pli value={0, 0}) : sum(value), l(NULL), r(NULL) {}
    Vertex(Vertex* l1, Vertex* r1) : sum(add(l1->sum, r1->sum)), l(l1), r(r1) {}
};

const int MAXN=100010, LOG=19;
int n, m, q, order[MAXN], tin[MAXN], tout[MAXN], assi[MAXN], up[LOG][MAXN], dep[MAXN], tim;
pii ch[MAXN];
vector<pii> g[MAXN];
Vertex* roots[MAXN];

Vertex* build(int tl, int tr){
    if(tl==tr) return new Vertex();
    int tm=(tl+tr)>>1;
    return new Vertex(build(tl, tm), build(tm+1, tr));
}

pli sum(Vertex* v, int tl, int tr, int l, int r){
    if(r<l) return {0, 0};
    if(l==tl && r==tr) return v->sum;
    int tm=(tl+tr)>>1;
    return add(sum(v->l, tl, tm, l, min(r, tm)), sum(v->r, tm+1, tr, max(l, tm+1), r));
}

Vertex* update(Vertex* v, int tl, int tr, int pos, pli value){
    if(tl==tr){
        assert(tl==pos);
        return new Vertex(add(v->sum, value));
    }
    int tm=(tl+tr)/2;
    if(pos<=tm) return new Vertex(update(v->l, tl, tm, pos, value), v->r);
    else return new Vertex(v->l, update(v->r, tm+1, tr, pos, value));
}

void dfs(int v, int p){
    up[0][v]=p;
    order[tim]=v;
    tin[v]=tim++;
    for(pii to:g[v]){
        if(to.F==p) assi[to.S]=v;
        else dep[to.F]=dep[v]+1, dfs(to.F, v);
    }
    tout[v]=tim;
}

int lca(int a, int b){
    if(dep[a]<dep[b]) swap(a, b);
    dforn(i, LOG) if(dep[a]-(1<<i)>=dep[b]) a=up[i][a];
    dforn(i, LOG) if(up[i][a]!=up[i][b]) a=up[i][a], b=up[i][b];
    return a==b? a : up[0][a];
}

pli query(Vertex* v, int a, int b){
    int lc=lca(a, b);
    return add(sum(v, 0, n, tin[lc]+1, tin[a]), sum(v, 0, n, tin[lc]+1, tin[b]));
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    forn(i, n-1){
        int a, b; scanf("%d %d", &a, &b); --a, --b;
        g[a].PB({b, i}), g[b].PB({a, i});
    }
    forn(i, m) scanf("%d %d", &ch[i].S, &ch[i].F), --ch[i].S;
    sort(ch, ch+m);
    dfs(0, 0);
    forn(i, LOG-1) forn(j, n) up[i+1][j]=up[i][up[i][j]];
    roots[0]=build(0, n);
    forn(i, m){
        Vertex* cur=roots[i];
        int v=assi[ch[i].S];
        cur=update(cur, 0, n, tin[v], {ch[i].F, 1});
        cur=update(cur, 0, n, tout[v], {-ch[i].F, -1});
        roots[i+1]=cur;
    }
    forn(i, q){
        int s, t, x; ll y; scanf("%d %d %d %lld", &s, &t, &x, &y); --s, --t;
        int lo=0, hi=m+1, best=0;
        while(hi-lo>1){
            int mid=(hi+lo)>>1;
            pli cost = query(roots[mid], s, t);
            if(cost.F<=y){
                lo=mid;
                best=max(best, cost.S);
            }
            else hi=mid;
        }
        int used=query(roots[m], s, t).S-best;
        if(used<=x) printf("%d\n", x-used);
        else printf("-1\n");
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:81:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         int a, b; scanf("%d %d", &a, &b); --a, --b;
      |                   ~~~~~^~~~~~~~~~~~~~~~~
currencies.cpp:84:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     forn(i, m) scanf("%d %d", &ch[i].S, &ch[i].F), --ch[i].S;
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:97:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         int s, t, x; ll y; scanf("%d %d %d %lld", &s, &t, &x, &y); --s, --t;
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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