oj.uz

답안 #972227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972227 2024-04-30T09:00:44 Z vjudge1 Two Currencies (JOI23_currencies) C++17
30 / 100
 3045 ms 81396 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 < 19; 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20060 KB Output is correct
2 Correct 4 ms 18012 KB Output is correct
3 Correct 4 ms 18012 KB Output is correct
4 Correct 4 ms 18012 KB Output is correct
5 Correct 27 ms 18872 KB Output is correct
6 Correct 36 ms 18780 KB Output is correct
7 Incorrect 33 ms 19016 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 18008 KB Output is correct
2 Correct 38 ms 18780 KB Output is correct
3 Correct 37 ms 18780 KB Output is correct
4 Correct 37 ms 18780 KB Output is correct
5 Correct 2383 ms 62928 KB Output is correct
6 Incorrect 2464 ms 57332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20060 KB Output is correct
2 Correct 30 ms 21084 KB Output is correct
3 Correct 31 ms 19036 KB Output is correct
4 Correct 30 ms 19036 KB Output is correct
5 Correct 1909 ms 71532 KB Output is correct
6 Correct 1903 ms 71876 KB Output is correct
7 Correct 1998 ms 58648 KB Output is correct
8 Correct 2963 ms 80868 KB Output is correct
9 Correct 3003 ms 81396 KB Output is correct
10 Correct 3045 ms 81308 KB Output is correct
11 Correct 2391 ms 80672 KB Output is correct
12 Correct 2313 ms 80496 KB Output is correct
13 Correct 2260 ms 80828 KB Output is correct
14 Correct 2025 ms 80220 KB Output is correct
15 Correct 1797 ms 79748 KB Output is correct
16 Correct 2159 ms 80356 KB Output is correct
17 Correct 2110 ms 79660 KB Output is correct

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 20060 KB Output is correct
2 Correct 4 ms 18012 KB Output is correct
3 Correct 4 ms 18012 KB Output is correct
4 Correct 4 ms 18012 KB Output is correct
5 Correct 27 ms 18872 KB Output is correct
6 Correct 36 ms 18780 KB Output is correct
7 Incorrect 33 ms 19016 KB Output isn't correct
8 Halted 0 ms 0 KB -