QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105956 | #2065. Cyclic Distance | Scintilla | WA | 49ms | 31736kb | C++14 | 2.8kb | 2023-05-16 08:23:36 | 2023-05-16 08:23:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pb emplace_back
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl
using pii = pair <int, int>;
const int N = 2e5 + 10;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
return x * f;
}
int n, k;
vector <pii> e[N];
struct pq {
priority_queue <int, vector <int>, greater <int>> q;
int laz;
void push(int x) { q.push(x - laz); }
int top() { return q.top() + laz; }
void pop() { q.pop(); }
void down(int x) { laz += x; }
int size() { return q.size(); }
void clear() { while (q.size()) q.pop(); laz = 0; }
} ;
struct node {
pq q1, q2, q3;
void push(int x) {
q1.push(x);
if (q1.size() <= k / 2) return;
q2.push(q1.top()), q1.pop();
if (q2.size() <= k % 2) return;
q3.push(q2.top()), q2.pop();
if (q3.size() <= k / 2) return;
q3.pop();
}
void down(int x) {
q1.down(x), q3.down(-x);
}
int size() {
return q1.size() + q2.size() + q3.size();
}
int calc() {
int res = 0;
for (auto q : {q1, q2, q3}) {
while (q.size()) res += max(q.top(), 0ll), q.pop();
}
return res;
}
void clear() {
q1.clear(), q2.clear(), q3.clear();
}
void print() {
int res = 0;
cout << res << ' ';
auto q = q1;
while (q.size()) {
res += q.top(), q.pop();
cout << res << ' ';
}
q = q2;
while (q.size()) {
res += q.top(), q.pop();
cout << res << ' ';
}
q = q3;
while (q.size()) {
res += q.top(), q.pop();
cout << res << ' ';
}
cout << endl;
}
} f[N];
void merge(int u, int v) {
if (f[u].size() < f[v].size()) swap(f[u], f[v]);
while (f[v].q1.size()) f[u].push(f[v].q1.top()), f[v].q1.pop();
while (f[v].q2.size()) f[u].push(f[v].q2.top()), f[v].q2.pop();
while (f[v].q3.size()) f[u].push(f[v].q3.top()), f[v].q3.pop();
}
void dfs(int u, int fa) {
for (auto [v, w] : e[u]) if (v != fa) {
dfs(v, u), f[v].down(2 * w), merge(u, v);
}
f[u].push(0);
// pv(u);
// f[u].print();
}
void solve() {
n = read(), k = read();
rep(i, 1, n) f[i].clear(), e[i].clear();
rep(i, 1, n - 1) {
int u = read(), v = read(), w = read();
e[u].pb(mp(v, w)), e[v].pb(mp(u, w));
}
dfs(1, 0);
printf("%lld\n", f[1].calc());
}
signed main() {
for (int tc = read(); tc; -- tc) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 31724kb
input:
1 5 3 1 2 4 1 3 1 1 4 8 4 5 9
output:
44
result:
ok single line: '44'
Test #2:
score: -100
Wrong Answer
time: 49ms
memory: 31736kb
input:
57206 3 2 1 2 574927 2 3 406566 2 2 1 2 308806 4 3 1 2 312588 2 3 500141 2 4 53602 3 3 1 2 797183 2 3 944061 5 3 1 2 624010 2 3 488613 3 4 734514 4 5 497493 5 4 1 2 540278 2 3 488655 2 4 228989 2 5 653896 2 2 1 2 569117 4 2 1 2 821764 2 3 499471 1 4 549060 2 2 1 2 991159 2 2 1 2 482941 5 4 1 2 30462...
output:
1962986 617612 1732662 3482488 4689260 4446214 1138234 3740590 1982318 965882 3418504 5026562 1623414 1885106 1952142 4012796 1691896 3102076 2380932 3076270 5697196 7258020 879020 2500212 3613854 1358950 1182198 2273662 2331560 1681964 8917452 2373066 3163042 3104226 3642898 3162310 5058442 3669186...
result:
wrong answer 6th lines differ - expected: '3823636', found: '4446214'