QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#304140 | #6332. Two Currencies | training4usaco | 0 | 7ms | 16052kb | C++17 | 3.9kb | 2024-01-13 14:51:24 | 2024-01-13 14:51:25 |
Judging History
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 = 7e6 + 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 u, int l, int r, int val) {
u = newnode(u);
if(l == r) {
++sz[u]; sum[u] += l;
return u;
}
int mid = (l + r) / 2;
if(val <= mid) lc[u] = upd(lc[u], l, mid, val);
else rc[u] = upd(rc[u], 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 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: 7ms
memory: 16052kb
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%