QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#292539 | #7118. Closing Time | training4usaco | 0 | 148ms | 48424kb | C++20 | 4.1kb | 2023-12-28 07:20:37 | 2023-12-28 07:20:38 |
Judging History
你现在查看的是测评时间为 2023-12-28 07:20:38 的历史记录
- [2024-04-29 19:10:22]
- 管理员手动重测该提交记录
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-12-28 07:20:37]
- 提交
answer
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
//#define int long long
typedef long long ll;
#define pii pair<ll, ll>
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
const int MAXN = 2e5 + 5;
const int MAXM = 4e6 + 5; // implicit segtree
const int MAX = 1e12 + 5;
ll dist[MAXN][2];
ll a[MAXN], b[MAXN]; // 2 costs
int ans, ans2; // no overlap, overlap
vector<pii> adj[MAXN];
vector<int> vals;
ll have;
ll tot = 1;
ll val[MAXM], cnt[MAXM];
ll lc[MAXM], rc[MAXM];
void check() {
if(tot >= MAXM) while(true) cout << "oof";
}
void pull(ll u) {
val[u] = val[lc[u]] + val[rc[u]];
cnt[u] = cnt[lc[u]] + cnt[rc[u]];
}
void ins(ll u, ll l, ll r, ll pos, ll freq) { // segtree indexed by val so pos = val
check();
if(l == r) {
// cout << "updating with " << pos << " " << freq << endl;
val[u] += pos * freq;
cnt[u] += freq;
return;
}
ll mid = (l + r) / 2;
if(pos <= mid) {
if(lc[u] == 0) lc[u] = ++tot;
ins(lc[u], l, mid, pos, freq);
}
else {
if(rc[u] == 0) rc[u] = ++tot;
ins(rc[u], mid + 1, r, pos, freq);
}
pull(u);
}
int walk(ll u, ll l, ll r) {
if(u == 0) return 0;
// cout << u << " " << l << " " << r << " " << val[u] << " " << cnt[u] << endl;
if(l == r) {
// cout << cnt[u] << " " << have << " " << l << endl;
ll sub = min(cnt[u], have / l);
have -= l * sub;
// cout << "returning " << sub << endl;
return sub;
}
ll mid = (l + r) / 2;
ll ret = 0;
if(val[lc[u]] > have) return walk(lc[u], l, mid);
// cout << "left val: " << val[lc[u]] << " node, lc: " << u << " " << lc[u] << endl;
have -= val[lc[u]];
if(have) return cnt[lc[u]] + walk(rc[u], mid + 1, r);
return cnt[lc[u]];
}
void dfs(int u, int p, int type) {
for(auto [v, w] : adj[u]) {
if(v == p) continue;
dist[v][type] = dist[u][type] + w;
dfs(v, u, type);
}
}
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
for(int i = 0; i < n - 1; ++i) {
adj[u[i]].push_back({v[i], w[i]});
adj[v[i]].push_back({u[i], w[i]});
}
dfs(x, -1, 0); dfs(y, -1, 1);
for(int i = 0; i < n; ++i) {
a[i] = min(dist[i][0], dist[i][1]);
b[i] = max(dist[i][0], dist[i][1]);
}
// seperate
vector<ll> sortedDists;
for(int i = 0; i < n; ++i) {
sortedDists.push_back(dist[i][0]); sortedDists.push_back(dist[i][1]);
}
sort(all(sortedDists));
ll tot = k;
for(auto val : sortedDists) {
if(tot >= val) {
++ans; tot -= val;
}
else break;
}
// overlap
bool flag = false;
ll distXY = dist[y][0]; // dist between x,y
// cout << "dist between x,y: " << distXY << endl;
for(int i = 0; i < n; ++i) {
if(dist[i][0] + dist[i][1] == distXY) { // on the path
// cout << "node " << i << " is on path" << endl;
k -= a[i]; ++ans2; // forced
if(k < 0) flag = true;
ins(1, 0, MAX, b[i] - a[i], 1);
// cout << "need " << b[i] - a[i] << " to turn to 2" << endl;
}
else {
ins(1, 0, MAX, a[i], 1);
// cout << "need " << a[i] << " for extra" << endl;
}
}
// cout << "total val of tree: " << val[1] << endl;
//
// cout << "forced overlap: " << ans2 << endl;
// cout << "have " << k << " left " << endl;
have = k;
// cout << "have: " << have << endl;
ans2 += walk(1, 0, MAX);
// cout << "total overlap ans: " << ans2 << endl;
if(flag) ans2 = 0;
return max(ans, ans2);
}
//signed main() {
// int n, x, y, k; cin >> n >> x >> y >> k;
//
// vector<int> u(n - 1), v(n - 1), w(n - 1);
//
// for(int i = 0; i < n - 1; ++i) cin >> u[i];
// for(int i = 0; i < n - 1; ++i) cin >> v[i];
// for(int i = 0; i < n - 1; ++i) cin >> w[i];
//
// cout << max_score(n, x, y, k, u, v, w) << endl;
//}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 8
Accepted
time: 141ms
memory: 47364kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 200000 31011 61157 8517583098 31011 129396 964383 1655 129396 331139 1655 191487 566483 110385 191487 865248 43212 110385 542661 43212 81682 13766 81682 91774 546589 91774 124706 780638 124706 175650 118706 10421 175650 615314 10421 151953 436270 140430 151...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 451
result:
ok
Test #2:
score: 0
Accepted
time: 148ms
memory: 48424kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 200000 97133 170892 35489415917 114511 170892 730058 34783 114511 435023 34783 47301 562314 47301 162600 457629 44856 162600 365133 44856 133801 83016 117539 133801 124222 117539 128719 199821 77871 128719 703141 77871 133155 624331 7211 133155 138691 7211 ...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 650
result:
ok
Test #3:
score: -8
Runtime Error
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 200 1000 611 992 5736784 504 611 954658 504 936 219278 502 936 632439 393 502 177662 267 393 570266 267 291 941365 291 310 168052 310 765 253098 635 765 724932 274 635 842125 274 799 848645 39 799 433118 39 940 705598 553 940 564063 553 960 69665 917 960 6904...
output:
result:
Subtask #2:
score: 0
Wrong Answer
Test #4:
score: 0
Wrong Answer
time: 0ms
memory: 8424kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 50 23 25 382806473 0 1 375710 1 2 898637 2 3 10402 3 4 536577 4 5 385023 5 6 71075 6 7 543368 7 8 301497 8 9 174394 9 10 711312 10 11 923006 11 12 675532 12 13 838667 13 14 565729 14 15 979816 15 16 862618 16 17 576015 17 18 177751 18 19 306989 19 20 881492...
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 71
result:
wrong answer 1st lines differ - on the 1st token, expected: '96', found: '71'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 3ms
memory: 8380kb
input:
cc61ad56a4797fb3f5c9529f73ce6fcedd85669b 1 4 0 1 9 0 2 2 1 2 3 2 3 3
output:
081ce3c351cbf526b37954b9ad30f2b531a7585c OK 5
result:
wrong answer 1st lines differ - on the 1st token, expected: '6', found: '5'
Subtask #6:
score: 0
Skipped
Dependency #2:
0%
Subtask #7:
score: 0
Skipped
Dependency #3:
0%
Subtask #8:
score: 0
Skipped
Dependency #4:
0%
Subtask #9:
score: 0
Skipped
Dependency #1:
0%