oj.uz

답안 #972223

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
972223 2024-04-30T08:58:32 Z vjudge1 Two Currencies (JOI23_currencies) C++17
30 / 100
 2714 ms 81140 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[400006], 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[300005], rg[300005];
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 <= 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]){
                if(l[to] + 1 >= r[to]) continue;
                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 4 ms 20572 KB Output is correct
2 Correct 4 ms 22620 KB Output is correct
3 Correct 4 ms 20572 KB Output is correct
4 Correct 3 ms 18524 KB Output is correct
5 Correct 21 ms 19292 KB Output is correct
6 Correct 31 ms 19292 KB Output is correct
7 Incorrect 26 ms 19292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18524 KB Output is correct
2 Correct 27 ms 19292 KB Output is correct
3 Correct 27 ms 21328 KB Output is correct
4 Correct 28 ms 19288 KB Output is correct
5 Correct 2119 ms 65548 KB Output is correct
6 Incorrect 2250 ms 59344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20568 KB Output is correct
2 Correct 24 ms 19544 KB Output is correct
3 Correct 23 ms 21536 KB Output is correct
4 Correct 23 ms 19528 KB Output is correct
5 Correct 1667 ms 74796 KB Output is correct
6 Correct 1582 ms 72524 KB Output is correct
7 Correct 1781 ms 57592 KB Output is correct
8 Correct 2559 ms 80696 KB Output is correct
9 Correct 2608 ms 80820 KB Output is correct
10 Correct 2714 ms 81140 KB Output is correct
11 Correct 2209 ms 80728 KB Output is correct
12 Correct 2110 ms 80456 KB Output is correct
13 Correct 2124 ms 80556 KB Output is correct
14 Correct 1899 ms 80292 KB Output is correct
15 Correct 1732 ms 76804 KB Output is correct
16 Correct 1999 ms 77648 KB Output is correct
17 Correct 2009 ms 77336 KB Output is correct

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 20572 KB Output is correct
2 Correct 4 ms 22620 KB Output is correct
3 Correct 4 ms 20572 KB Output is correct
4 Correct 3 ms 18524 KB Output is correct
5 Correct 21 ms 19292 KB Output is correct
6 Correct 31 ms 19292 KB Output is correct
7 Incorrect 26 ms 19292 KB Output isn't correct
8 Halted 0 ms 0 KB -