oj.uz

Submission #972231

# Submission time Handle Problem Language Result Execution time Memory
972231 2024-04-30T09:04:01 Z vjudge1 Two Currencies (JOI23_currencies) C++17
30 / 100
 3324 ms 79148 KB 
#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 < 20; i++){    
        for(int j = 1; j <= m; j++)  d[j].clear();
        for(int j = 1; j <= 3 * dl; 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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20060 KB Output is correct
2 Correct 5 ms 18012 KB Output is correct
3 Correct 4 ms 18168 KB Output is correct
4 Correct 3 ms 18008 KB Output is correct
5 Correct 28 ms 18804 KB Output is correct
6 Correct 37 ms 18780 KB Output is correct
7 Incorrect 38 ms 20824 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18012 KB Output is correct
2 Correct 38 ms 16980 KB Output is correct
3 Correct 40 ms 16952 KB Output is correct
4 Correct 43 ms 16948 KB Output is correct
5 Correct 2674 ms 62972 KB Output is correct
6 Incorrect 2628 ms 57204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15964 KB Output is correct
2 Correct 31 ms 16984 KB Output is correct
3 Correct 32 ms 16988 KB Output is correct
4 Correct 32 ms 17184 KB Output is correct
5 Correct 2077 ms 72260 KB Output is correct
6 Correct 1929 ms 69624 KB Output is correct
7 Correct 2081 ms 54952 KB Output is correct
8 Correct 3322 ms 78916 KB Output is correct
9 Correct 3201 ms 79080 KB Output is correct
10 Correct 3324 ms 79148 KB Output is correct
11 Correct 2490 ms 78552 KB Output is correct
12 Correct 2624 ms 78636 KB Output is correct
13 Correct 2520 ms 78468 KB Output is correct
14 Correct 2205 ms 78472 KB Output is correct
15 Correct 2041 ms 78092 KB Output is correct
16 Correct 2421 ms 78800 KB Output is correct
17 Correct 2392 ms 78712 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20060 KB Output is correct
2 Correct 5 ms 18012 KB Output is correct
3 Correct 4 ms 18168 KB Output is correct
4 Correct 3 ms 18008 KB Output is correct
5 Correct 28 ms 18804 KB Output is correct
6 Correct 37 ms 18780 KB Output is correct
7 Incorrect 38 ms 20824 KB Output isn't correct
8 Halted 0 ms 0 KB -