QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331497#7415. Fast Spanning TreeyllcmTL 12ms184352kbC++142.9kb2024-02-18 12:10:172024-02-18 12:10:17

Judging History

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

  • [2024-02-18 12:10:17]
  • 评测
  • 测评结果:TL
  • 用时:12ms
  • 内存:184352kb
  • [2024-02-18 12:10:17]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 3e5 + 10;
const int Mx = 1e6;
int n, m;
int a[N], f[N], sum[N], vis[N], le[N], sz[N];
struct Edge {int u, v, w, lu, lv;};
Edge e[N];
int tot;
struct Node {
  int ls, rs, d;
  pii w;
}nd[N * 30];
int New(pii x) {
  int cur = ++tot;
  nd[cur] = {0, 0, 1, x};
  return cur;
}
int merge(int x, int y) {
  if(!x || !y)return x + y;
  if(nd[x].w > nd[y].w)swap(x, y);
  nd[x].rs = merge(nd[x].rs, y);
  if(nd[nd[x].ls].d < nd[nd[x].rs].d)swap(nd[x].ls, nd[x].rs);
  nd[x].d = nd[nd[x].rs].d + 1;
  return x;
}
int st[N], del[N];
// priority_queue<pii, vector<pii>, greater<pii> > st[N], del[N];
int find(int x) {return f[x] == x ? x : f[x] = find(f[x]);}
int pop(int x) {return merge(nd[x].ls, nd[x].rs);}
signed main() {
  n = read(); m = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  priority_queue<int, vector<int>, greater<int> > q;
  for(int i = 1; i <= n; i++)f[i] = i;
  for(int i = 1; i <= m; i++) {
    int u = read(), v = read(), w = read();
    e[i] = {u, v, w};
    if(a[u] + a[v] >= w)q.push(i);
    else {
      int val = (w - a[u] - a[v] + 1) / 2;
      st[u] = merge(st[u], New({e[i].lu = a[u] + val, i}));
      st[v] = merge(st[v], New({e[i].lv = a[v] + val, i}));
    }
  }
  vector<int> ans;
  auto flush = [&](int u) {
    while(st[u] && del[u] && nd[st[u]].w == nd[del[u]].w)
      st[u] = pop(st[u]), del[u] = pop(del[u]);
    return ;
  };
  auto unionn = [&](int u, int v) {
    u = find(u); v = find(v);
    if(sz[u] < sz[v])swap(u, v);
    f[v] = u; a[u] = min(a[u] + a[v], Mx);
    st[u] = merge(st[u], st[v]);
    del[u] = merge(del[u], del[v]);
    flush(u);
    while(st[u] && nd[st[u]].w.FR <= a[u]) {
      int id = nd[st[u]].w.SE;
      int x = find(e[id].u), y = find(e[id].v);
      // cerr << u << ' ' << id << ' ' << x << ' ' << y << endl;
      del[x] = merge(del[x], New({e[id].lu, id}));
      del[y] = merge(del[y], New({e[id].lv, id}));
      flush(u);
      if(x == y)continue;
      if(a[x] + a[y] >= e[id].w)q.push(id);
      else {
        int val = (e[id].w - a[x] - a[y] + 1) / 2;
        st[x] = merge(st[x], New({e[id].lu = a[x] + val, id}));
        st[y] = merge(st[x], New({e[id].lv = a[y] + val, id}));
      }
    }
    return ;
  };
  while(q.empty() == false) {
    int id = q.top(); q.pop();
    if(find(e[id].u) == find(e[id].v))continue;
    ans.pb(id); 
    unionn(e[id].u, e[id].v);
  }
  printf("%lu\n", ans.size());
  for(int x : ans)printf("%d ", x); putchar('\n');
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 184352kb

input:

5 5
1 4 3 4 0
4 5 5
3 1 1
2 5 2
4 3 1
4 1 4

output:

4
2 3 1 4 

result:

ok 5 number(s): "4 2 3 1 4"

Test #2:

score: 0
Accepted
time: 3ms
memory: 183996kb

input:

3 5
3 2 2
1 2 6
1 2 6
1 2 3
1 2 6
2 3 6

output:

2
3 5 

result:

ok 3 number(s): "2 3 5"

Test #3:

score: 0
Accepted
time: 12ms
memory: 183936kb

input:

10 20
4 6 6 1 7 9 1 8 7 9
5 3 2
1 10 10
5 6 7
9 6 9
3 1 1
6 8 1
5 7 0
9 5 4
10 3 4
8 6 8
3 10 6
5 3 8
3 7 9
1 9 10
10 1 0
5 7 6
6 10 1
6 5 9
5 8 2
9 2 4

output:

8
1 2 3 4 5 6 7 20 

result:

ok 9 numbers

Test #4:

score: -100
Time Limit Exceeded

input:

10 20
0 10 4 6 2 0 2 0 2 8
5 10 8
7 1 6
10 5 0
9 8 0
5 8 4
5 1 8
10 3 6
5 4 3
9 2 6
10 3 6
4 3 1
3 10 3
6 1 3
3 2 5
6 9 2
4 2 5
10 6 5
8 6 3
2 1 0
2 3 6

output:


result: