oj.uz

답안 #971655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971655 2024-04-29T06:45:25 Z vjudge1 Two Currencies (JOI23_currencies) C++17
28 / 100
 357 ms 65024 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[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(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;
        }
        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";
    }
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 17500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 17500 KB Output is correct
2 Correct 7 ms 18012 KB Output is correct
3 Correct 7 ms 18012 KB Output is correct
4 Correct 6 ms 18008 KB Output is correct
5 Correct 301 ms 47220 KB Output is correct
6 Correct 258 ms 41668 KB Output is correct
7 Correct 243 ms 44144 KB Output is correct
8 Correct 230 ms 44100 KB Output is correct
9 Correct 247 ms 44004 KB Output is correct
10 Correct 333 ms 47780 KB Output is correct
11 Correct 308 ms 47812 KB Output is correct
12 Correct 357 ms 47928 KB Output is correct
13 Correct 300 ms 47812 KB Output is correct
14 Correct 303 ms 47808 KB Output is correct
15 Correct 347 ms 58020 KB Output is correct
16 Correct 313 ms 65024 KB Output is correct
17 Correct 316 ms 63320 KB Output is correct
18 Correct 324 ms 53688 KB Output is correct
19 Correct 343 ms 53436 KB Output is correct
20 Correct 308 ms 53712 KB Output is correct
21 Correct 264 ms 52632 KB Output is correct
22 Correct 302 ms 53056 KB Output is correct
23 Correct 293 ms 52780 KB Output is correct
24 Correct 267 ms 52836 KB Output is correct
25 Correct 292 ms 53144 KB Output is correct
26 Correct 292 ms 53072 KB Output is correct
27 Correct 301 ms 53080 KB Output is correct
28 Correct 286 ms 52804 KB Output is correct
29 Correct 320 ms 52872 KB Output is correct
30 Correct 307 ms 53020 KB Output is correct
31 Correct 303 ms 53220 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 17500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 17500 KB Output isn't correct
2 Halted 0 ms 0 KB -