Submission #1104740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104740		InvMOD	Two Currencies (JOI23_currencies)	C++14	100 / 100	1306 ms	41184 KiB

currencies

#include<bits/stdc++.h>

//#define int long long

using namespace std;

using ll = long long;

struct Query{
    int s, t;
    ll gold, silver;
};

const int N = 1e5+5;

int n, m, q, timerDFS, curChain;

int h[N], sz[N];
int tin[N], id[N], par[N], head[N];

int ql[N], qr[N], rem[N];

ll bit[2][N];
Query Q[N];

vector<int> adj[N], md[N];

pair<int,int> E[N], P[N];

void update(int t, int p, ll val){
    for(; p <= timerDFS; p += (p & (-p))) bit[t][p] += val;
    return;
}

ll get(int t, int p){
    ll res = 0;
    for(; p; p -= (p & (-p))) res += bit[t][p];
    return res;
}

ll get_range(int t, int l, int r){
    return get(t, r) - get(t, l-1);
}

void dfs(int x = 1, int p = -1){
    sz[x] = 1;
    for(int v : adj[x])if(v != p){
        par[v] = x;
        h[v] = h[x] + 1;
        dfs(v, x);
        sz[x] += sz[v];
    }
    return;
}

void decompose(int x = 1, int p = -1){
    if(!head[curChain]) head[curChain] = x;
    id[x] = curChain;
    tin[x] = ++timerDFS;
    int nxt = 0; for(int v : adj[x])if(v != p && sz[v] > sz[nxt]) nxt = v;
    if(nxt) decompose(nxt, x);
    for(int v : adj[x])if(v != p && v != nxt) ++curChain, decompose(v, x);
    return;
}

int get_LCA(int u, int v){
    while(id[u] != id[v]){
        if(id[u] > id[v]) u = par[head[id[u]]];
        else v = par[head[id[v]]];
    }
    return h[u] < h[v] ? u : v;
}

ll get_Path(int u, int v, int type){
    int lca = get_LCA(u, v);
    ll res = 0;
    while(id[u] != id[lca]){
        res = res + get_range(type, tin[head[id[u]]], tin[u]);
        u = par[head[id[u]]];
    }
    while(id[v] != id[lca]){
        res = res + get_range(type, tin[head[id[v]]], tin[v]);
        v = par[head[id[v]]];
    }
    if(h[u] > h[v]) swap(u, v);
    res = res + get_range(type, tin[u]+1, tin[v]);
    return res;
}

void solve()
{
    cin >> n >> m >> q;

    for(int i = 1; i < n; i++){
        int u,v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        E[i] = make_pair(u, v);
    }

    timerDFS = 0, curChain = 0;
    dfs(), decompose();

    for(int i = 1; i <= m; i++){
        int idEdge,C; cin >> idEdge >> C;
        P[i] = make_pair((h[E[idEdge].first] < h[E[idEdge].second] ? E[idEdge].second : E[idEdge].first), C);
        update(0, tin[P[i].first], 1);
    }

    sort(P+1, P+1+m, [&](pair<int,int> x, pair<int,int> y){
            return x.second < y.second;
    });

    for(int i = 1; i <= q; i++){
        cin >> Q[i].s >> Q[i].t >> Q[i].gold >> Q[i].silver;
        ql[i] = -1, qr[i] = m+1;
    }

    bool changed = true;
    while(changed){

        changed = false;

        for(int i = 1; i <= q; i++){
            if(ql[i]+1 < qr[i]){
                changed = true;
                md[ql[i]+qr[i]>>1].push_back(i);
            }
        }

        for(int i = 0; i <= m; i++){
            if(i){
                update(0, tin[P[i].first], -1);
                update(1, tin[P[i].first], +P[i].second);
            }

            while(md[i].size()){
                int id = md[i].back(); md[i].pop_back();

                ll val = get_Path(Q[id].s, Q[id].t, 1);
                if(val <= Q[id].silver){
                    ql[id] = i;
                    rem[id] = Q[id].gold - get_Path(Q[id].s, Q[id].t, 0);
                }
                else{
                    qr[id] = i;
                }
            }
        }

        for(int i = 1; i <= m; i++){
            update(0, tin[P[i].first], +1);
            update(1, tin[P[i].first], -P[i].second);
        }
    }


    for(int i = 1; i <= q; i++){
        cout << max(rem[i], -1) <<"\n";
    }
}

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

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

currencies.cpp: In function 'void solve()':
currencies.cpp:127:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |                 md[ql[i]+qr[i]>>1].push_back(i);
      |                    ~~~~~^~~~~~
currencies.cpp: In function 'int32_t main()':
currencies.cpp:169:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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