Submission #971656

#	Time	Username	Problem	Language	Result	Execution time	Memory
971656		vjudge1	Two Currencies (JOI23_currencies)	C++17	38 / 100	365 ms	58840 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[200005];
ll p[100005], c[100005], s[100005], t[100005], x[100005], y[100005], h[100005], pp[100005];
pair<ll, ll> mn[1000005];
vector<ll> v;
map<pair<int, int>, int> mp;
int kol[100005], dp[100005];
void dfs(int k, int pr){
    v.push_back(k);
    pp[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);
        v.push_back(k);
    }
}
void up(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;
    up(l, mid, pos, num, ind, vv * 2);
    up(mid + 1, r, pos, num, ind, vv * 2 + 1);
    mn[vv] = min(mn[vv * 2], mn[vv * 2 + 1]);
}
pair<int, int> sbor(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(sbor(l, mid, l1, r1, vv * 2), sbor(mid + 1, r, l1, r1, vv * 2 + 1));
}
vector<ll> ss[100005];
int lf[1000005];
set<int> st;
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;
    }
    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]);
    }
    for(int i = 1; i <= q; i++)
        cin >> s[i] >> t[i] >> x[i] >> y[i];
    v.push_back(1);
    dfs(1, 0);
    for(int i = 1; i < int(v.size()); i++){
        up(1, int(v.size()) - 1, i, h[v[i]], v[i], 1);
        if(lf[v[i]] == 0) lf[v[i]] = i;
    }
    int d = v.size();
    for(int i = 1; i <= q; i++){
        int l = min(lf[s[i]], lf[t[i]]);
        int r = max(lf[s[i]], lf[t[i]]);
        auto it = sbor(1, d - 1, l, r, 1);
        int lca = it.second;
        if(n <= 2000 && m <= 2000 && q <= 2000){
            vector<ll> vv;
            l = s[i], r = t[i];
            while(l != lca){
                for(ll to : ss[mp[{l, pp[l]}]])
                    vv.push_back(to);
                l = pp[l];
            }
            while(r != lca){
                for(ll to : ss[mp[{r, pp[r]}]])
                    vv.push_back(to);
                r = pp[r];
            }
            sort(vv.rbegin(), vv.rend());
            while(!vv.empty()){
                if(y[i] >= vv.back()){
                    y[i] -= vv.back();
                    vv.pop_back();
                }
                else break;
            }
            x[i] -= int(vv.size());
            if(x[i] < 0) cout << -1 << "\n";
            else cout << x[i] << "\n";
            continue;
        }
        if(int(st.size()) == 1){
            ll dist = kol[s[i]] - kol[lca] + kol[t[i]] - kol[lca];
            ll ost = x[i] - max(0ll, dist - y[i] / c[1]);
            if(ost < 0) cout << -1 << "\n";
            else cout << ost << "\n";
            continue;
        }
    }
}

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