QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#304128#6332. Two Currenciestraining4usaco0 4ms16620kbC++174.0kb2024-01-13 14:44:032024-01-13 14:44:04

Judging History

你现在查看的是最新测评结果

  • [2024-01-13 14:44:04]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:16620kb
  • [2024-01-13 14:44:03]
  • 提交

answer

#include <iostream>
#include <vector>
using namespace std;

#define int long long
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXM = 6e6 + 5;
const int MAXN = 1e5 + 5;
const int INF = 1e9 + 7;

int n, m, q;
int tot = 0;

int root[MAXN];
vector<int> adj[MAXN];
pii edges[MAXN];
int sz[MAXN], sum[MAXN], lc[MAXN], rc[MAXN];
vector<int> need[MAXN];

int newnode(int u) {
    sz[++tot] = sz[u]; sum[tot] = sum[u]; lc[tot] = lc[u]; rc[tot] = rc[u];
    return tot;
}

void pull(int u) {
    sz[u] = sz[lc[u]] + sz[rc[u]];
    sum[u] = sum[lc[u]] + sum[rc[u]];
}

int upd(int node, int l, int r, int val) {
    int u = newnode(node);

    if(l == r) {
        ++sz[u]; sum[u] += l;
        return u;
    }

    int mid = (l + r) / 2;
    if(val <= mid) lc[u] = upd(lc[node], l, mid, val);
    else rc[u] = upd(rc[node], mid + 1, r, val);
    pull(u); return u;
}

int walk(int u, int v, int lca, int l, int r, int val) {    // binary search builtin to pst
    if(l == r) {
//        cout << "returning " << min(sz[u] + sz[v] - 2 * sz[lca], val / l) << endl;
//        return min(sz[u] + sz[v] - 2 * sz[lca], val / l);

        int ret = sz[u] + sz[v] - 2 * sz[lca];
        
        if(val / l < ret) ret = val / l;
        return ret;
    }

    int lsum = sum[lc[u]] + sum[lc[v]] - 2 * sum[lc[lca]];
    int lsz = sz[lc[u]] + sz[lc[v]] - 2 * sz[lc[lca]];

//    cout << lsum << ", " << lsz << endl;

    int mid = (l + r) / 2;
    if(lsum <= val) {
//        cout << "going into right child" << endl;
        return lsz + walk(rc[u], rc[v], rc[lca], mid + 1, r, val - lsum);
    }
//    cout << "going into left child" << endl;
    return walk(lc[u], lc[v], lc[lca], l, mid, val);
}

int heavy[MAXN], dep[MAXN], subsz[MAXN], par[MAXN];
int head[MAXN];
int timer = 0, tin[MAXN];

void dfssz(int u, int p) {
    dep[u] = dep[p] + 1;
    par[u] = p; subsz[u] = 1;
    for(auto v : adj[u]) {
        if(v == p) continue;
        dfssz(v, u);
        subsz[u] += subsz[v];
    }
}

void hld(int u, int p, int top) {
    // cout << u << " " << p << " " << top << endl;
    head[u] = top;

    int hchild = -1, hsz = -1;

    for(auto v : adj[u]) {
        if(v == p) continue;
        if(subsz[v] > hsz) {
            hsz = subsz[v];
            hchild = v;
        }
    }

    // cout << hchild << " " << hsz << endl;

    if(hchild == -1) return;

    hld(hchild, u, top);
    for(auto v : adj[u]) {
        if(v == p || v == hchild) continue;
        hld(v, u, v);
    }
}

int query(int u, int v) {
    while(head[u] != head[v]) {
        // cout << u << " " << v << endl;
        if(dep[head[u]] < dep[head[v]]) swap(u, v);
        u = par[head[u]];
    }

    if(dep[u] > dep[v]) swap(u, v);
    return u;
}

void dfs(int u, int p) {
//    cout << "node " << u << endl;
    for(auto val : need[u]) {
//        cout << "val: " << val << endl;
        root[u] = upd(root[u], 1, INF, val);
    }

    for(auto v : adj[u]) {
        if(v == p) continue;
        root[v] = root[u];
        dfs(v, u);
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m >> q;

    for(int i = 1; i < n; ++i) {
        cin >> edges[i].ff >> edges[i].ss;
        adj[edges[i].ff].push_back(edges[i].ss);
        adj[edges[i].ss].push_back(edges[i].ff);
    }

    dfssz(1, 1); hld(1, 1, 1);

    for(int i = 1; i <= m; ++i) {
        int a, b; cin >> a >> b;

        if(edges[a].ss == par[edges[a].ff]) need[edges[a].ff].push_back(b);
        need[edges[a].ss].push_back(b);
    }

    dfs(1, 1);

    while(q--) {
        int u, v, x, y; cin >> u >> v >> x >> y;

        int lca = query(u, v);

//        cout << "lca: " << lca << endl;

        int cost = (sz[root[u]] + sz[root[v]] - 2 * sz[root[lca]]) - walk(root[u], root[v], root[lca], 1, INF, y);
//        cout << "cost: " << cost << endl;
        if(cost > x) cout << -1 << endl;
        else cout << x - cost << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 16620kb

input:

1831 1865 1153
832 1698
1672 1619
634 920
328 1244
571 1279
1673 1815
1098 92
1320 432
244 636
991 1446
308 569
1118 1356
1733 71
497 1679
1699 635
1254 1295
853 345
364 1396
1183 1134
524 1557
1642 1262
1767 459
918 794
1644 539
902 1046
334 1789
1691 1548
1298 520
1763 216
1161 1065
682 1167
1282 ...

output:

378730605
649537044
339843141
362013697
600127619
123276007
749019778
-1
16
54569538
-1
26669081
22
255375699
-1
-1
-1
-1
427653834
-1
-1
0
-1
-1
-1
-1
-1
265022184
218253041
-1
7
849614439
-1
29092527
539604026
-1
-1
-1
-1
-1
4
-1
-1
10
-1
-1
-1
-1
-1
-1
-1
0
546008661
-1
-1
86261072
-1
448122840
8...

result:

wrong answer 8th numbers differ - expected: '22', found: '-1'

Subtask #2:

score: 0
Runtime Error

Test #32:

score: 0
Runtime Error

input:

99819 89735 60985
59741 24953
61387 12293
53761 1828
60970 60534
40598 48807
21876 21232
29527 13335
84269 40756
89571 12996
25757 40587
52477 63347
41372 69243
16391 58678
40854 39513
84384 91744
62938 60371
81932 45504
34121 54746
51945 14294
883 85344
78845 51797
45025 76590
37694 65493
4118 2588...

output:


result:


Subtask #3:

score: 0
Runtime Error

Test #59:

score: 0
Runtime Error

input:

95629 64841 64314
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%