QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105956#2065. Cyclic DistanceScintillaWA 49ms31736kbC++142.8kb2023-05-16 08:23:362023-05-16 08:23:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-16 08:23:39]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:31736kb
  • [2023-05-16 08:23:36]
  • 提交

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'