Submission #972234

#	Time	Username	Problem	Language	Result	Execution time	Memory
972234		vjudge1	Two Currencies (JOI23_currencies)	C++17	100 / 100	4062 ms	104656 KiB

currencies

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;
int tt = 1, n, m, q;
vector<int> g[100005];
ll p[100005], c[100005], s[100005], t[100005], x[100005], y[100005], h[100005], lk[500006], pred[100005];
pair<ll, ll> sum[2000005];
vector<ll> v, v1;
map<pair<int, int>, int> mp;
int kol[100005], dp[100005];
void dfs(int k, int pr){
    v.push_back(k);
    v1.push_back(k);
    pred[k] = pr;
    kol[k] += dp[mp[{k, pr}]];
    for(int to : g[k]){
        if(to == pr) continue;
        h[to] = h[k] + 1;
        kol[to] += kol[k];
        dfs(to, k);
        v1.push_back(k);
    }
    v.push_back(k);
}
pair<int, int> mn[2000005];

void up1(int l, int r, int pos, int num, int ind, int vv){
    if(l > pos || r < pos) return;
    if(l == r){
        mn[vv] = {num, ind};
        return; 
    }
    int mid = (l + r) / 2;
    up1(l, mid, pos, num, ind, vv * 2);
    up1(mid + 1, r, pos, num, ind, vv * 2 + 1);
    mn[vv] = min(mn[vv * 2], mn[vv * 2 + 1]);
}
pair<int, int> sbor1(int l, int r, int l1, int r1, int vv){
    if(l > r1 || l1 > r) return {1e9, 1e9};
    if(l >= l1 && r1 >= r) return mn[vv];
    int mid = (l + r) / 2;
    return min(sbor1(l, mid, l1, r1, vv * 2), sbor1(mid + 1, r, l1, r1, vv * 2 + 1));
}

void up(int l, int r, int pos, ll num, int vv){
    if(l > pos || r < pos) return;
    if(l == r){
        sum[vv].first += num;
        if(num > 0) sum[vv].second++;
        else sum[vv].second--;
        return; 
    }
    int mid = (l + r) / 2;
    up(l, mid, pos, num, vv * 2);
    up(mid + 1, r, pos, num, vv * 2 + 1);
    sum[vv].first = sum[vv * 2].first + sum[vv * 2 + 1].first;
    sum[vv].second = sum[vv * 2].second + sum[vv * 2 + 1].second;
}
pair<ll, ll> sbor(int l, int r, int l1, int r1, int vv){
    if(l > r1 || l1 > r) return {0, 0};
    if(l >= l1 && r1 >= r) return sum[vv];
    int mid = (l + r) / 2;
    pair<ll, ll> num1 = sbor(l, mid, l1, r1, vv * 2);
    pair<ll, ll> num2 = sbor(mid + 1, r, l1, r1, vv * 2 + 1);
    return {num1.first + num2.first, num1.second + num2.second};
}
vector<ll> ss[100005];
int lf[400005], rg[400005];
int l[100005], r[100005], res[100005];
set<int> st;
vector<int> d[100005];
pair<int, pair<int, int>> pp[100005];
pair<int, int> edge[100005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
        mp[{a, b}] = i;
        mp[{b, a}] = i;
        edge[i] = {a, b};
    }
    for(int i = 1; i <= m; i++){
        cin >> p[i] >> c[i];
        ss[p[i]].push_back(c[i]);
        dp[p[i]]++;
        st.insert(s[i]);
        pp[i] = {c[i], {p[i], i}};
    }
    for(int i = 1; i <= q; i++){
        l[i] = 0;
        r[i] = m + 1;
        cin >> s[i] >> t[i] >> x[i] >> y[i];
    }
    v.push_back(1);
    v1.push_back(1);
    dfs(1, 0);
    sort(pp + 1, pp + m + 1);
    for(int i = 1; i < int(v.size()); i++)
        if(lf[v[i]] == 0) lf[v[i]] = i;
    for(int i = int(v.size()) - 1; i >= 1; i--)
        if(rg[v[i]] == 0) rg[v[i]] = i;
    int dl1 = int(v1.size()) - 1;
    for(int i = 1; i <= dl1; i++){
        up1(1, dl1, i, h[v1[i]], v1[i], 1);
        if(lk[v1[i]] == 0) lk[v1[i]] = i;
    }
    int dl = int(v.size()) - 1;
    for(int i = 0; i < 18; i++){    
        for(int j = 1; j <= m; j++)  d[j].clear();
        for(int j = 1; j <= 2000000; j++) sum[j] = {0, 0};
        for(int j = 1; j <= q; j++){
            int mid = (l[j] + r[j]) / 2;
            d[mid].push_back(j);
        }
        for(int j = 1; j <= m; j++){
            int a = edge[pp[j].second.first].first, b = edge[pp[j].second.first].second, lc;
            if(h[a] > h[b]) swap(a, b);
            up(1, dl, lf[b], pp[j].first, 1);
            up(1, dl, rg[b], -pp[j].first, 1);
            for(int to : d[j]){
                int l1 = min(lk[s[to]], lk[t[to]]);
                int r1 = max(lk[s[to]], lk[t[to]]);
                auto it = sbor1(1, dl1, l1, r1, 1);
                int lca = it.second;
                ll dist1 = 0, dist2 = 0;
                if(lca != s[to]){
                    auto it1 = sbor(1, dl, lf[lca] + 1, lf[s[to]], 1);
                    dist1 += it1.first;
                    dist2 += it1.second;
                }
                if(lca != t[to]){
                    auto it1 = sbor(1, dl, lf[lca] + 1, lf[t[to]], 1);
                    dist1 += it1.first;
                    dist2 += it1.second;
                }
                if(dist1 <= y[to]){
                    l[to] = j;
                    res[to] = dist2;
                }
                else r[to] = j;
            }
        }
    }
    for(int i = 1; i <= q; i++){
        int l1 = min(lk[s[i]], lk[t[i]]);
        int r1 = max(lk[s[i]], lk[t[i]]);
        auto it = sbor1(1, dl1, l1, r1, 1);
        int lca = it.second;
        ll dist = kol[s[i]] - kol[lca] + kol[t[i]] - kol[lca];
        if(x[i] - max(0ll, dist - res[i]) >= 0) cout << x[i] - max(0ll, dist - res[i]) << "\n";
        else cout << -1 << "\n";
    }
}

Compilation message (stderr)

currencies.cpp: In function 'int main()':
currencies.cpp:146:90: warning: unused variable 'lc' [-Wunused-variable]
  146 |             int a = edge[pp[j].second.first].first, b = edge[pp[j].second.first].second, lc;
      |                                                                                          ^~

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