QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#329983#185. Bridgesjunbin0 1274ms10824kbC++145.0kb2024-02-17 10:16:452024-02-17 10:16:47

Judging History

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

  • [2024-02-17 10:16:47]
  • 评测
  • 测评结果:0
  • 用时:1274ms
  • 内存:10824kb
  • [2024-02-17 10:16:45]
  • 提交

answer

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <list>
#include<fstream>
#include <bitset>

using namespace std;  
using ll = long long;
using ull = unsigned long long;
#define pb push_back
#define P pair
#define V vector
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FFOR(i, a, b) for (int i = a; i <= b; ++i)

template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} 
  out << "]";
  return out;
}

const int N = 200000 + 10;
int ans[N], L[2010], R[2010], timing[N];
bool vis1[N], vis2[N];
vector<int> T[2010];

struct E {
  int u, v, w, t, i;
} e[N], ee[N];

struct Q {
  int u, w, t, i;
  bool operator< (const Q& other) {
    return w > other.w;
  }
} q[N];

bool comp1(E& e1, E& e2) {
  return e1.t < e2.t;
}

bool comp2(E& e1, E& e2) {
  return e1.w > e2.w;
}

//DSU
struct Node {
    int fax, fay, w, sz;
} stk[N];

int p[N], rk[N], sz[N]; 
int top = 0;
int find(int x) {
  return p[x] == x ? x : find(p[x]);
}

bool merge(int u, int v) {
  int fax = find(u), fay = find(v);
  if(rk[fax] > rk[fay]) {
    swap(fax, fay);
  }
  
  //注意这里,否则树的高度会不一样而导致TLE
  if(fax != fay) {
    stk[top++] = (Node){fax, fay, (rk[fax] == rk[fay]), sz[fay]};
    p[fax] = fay;
    sz[fay] += sz[fax];
    if(rk[fay] == rk[fax]) rk[fay]++;
    return true;
  }
  return false;
}

void undo() {
  while(top > 0) {
    top--;
    int fax = stk[top].fax, fay = stk[top].fay;
    p[fax] = fax;
    rk[fay] -= stk[top].w;
    sz[fay] = stk[top].sz;
  }
}
////////////////////////////////////////////////////////////////////

void init(int n, int m) {
  top = 0;
  for(int i = 0; i <= n; i++) {
    p[i] = i, sz[i] = 1, rk[i] = 0;
  }
  for(int i = 0; i <= m; i++) vis1[i] = false;
}

int cnt = 0;
void solve() {
  int n, m;
  scanf("%d%d", &n, &m);
  for(int i = 0; i < m; i++) {
    scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    e[i].t = 0;
    e[i].i = i;
  }
  
  int k = 0, ti = 0, o = 0;
  scanf("%d", &o);
  for(int i = 0; i < o; i++) {
    int op;
    scanf("%d", &op);
    if(op == 1) {
      int ith, w;
      scanf("%d%d", &ith, &w);
      e[m] = {e[ith - 1].u, e[ith - 1].v, w, ++ti, ith - 1};
      m++;
    } else {
      scanf("%d%d", &q[k].u, &q[k].w);
      q[k].t = ++ti;
      q[k].i = k;
      k++;
    }
  }

  for(int i = 0; i < m; i++) {
    ee[i] = {e[i].u, e[i].v, e[i].w, e[i].t, e[i].i};
  }

  sort(e, e + m, comp1); //按w 从大到小排序
  sort(q, q + k); //按t 从小到大排序

  //分块范围初始化
  int s = sqrt(m);
  int t = 0;
  for(int i = 0; i < m; i += s) {
    L[t] = i;
    R[t] = min(m - 1, i + s - 1);
    t++;
  }
  //分块分配处理
  for(int i = 0; i < k; i++) {
    int j = 0;
    while(j < t && e[R[j]].t <= q[i].t) j++;
    T[min(j, t - 1)].push_back(i);
  }
  
  //for(int i = 0; i < t; i++) cout << i << " " << T[i] << endl;
  
  for(int i = 0; i < t; i++) {
    int l = L[i], r = R[i];
    init(n, m);
    sort(e, e + l, comp2);
    cout << endl;
    for(int o = l; o <= r; o++) {
      vis1[e[o].i] = true;
    }

    vector<E> cur;
    int j = 0;
    for(int& x : T[i]) {
      int u = q[x].u, w = q[x].w, idx = q[x].i;
      
      while(j < l && e[j].w >= w) {
        if(e[j].w != ee[e[j].i].w) { //not the newest
        } else {
          if(vis1[e[j].i]) {
            cur.push_back(e[j]);
          } else {
            merge(e[j].u, e[j].v);
          }
        }
        j++;
      }
      
      top = 0;
      for(int o = r; o >= l; o--) {
        if(e[o].t <= q[x].t) {
          if(!vis2[e[o].i]) {
            if(e[o].w >= w) {
              merge(e[o].u, e[o].v);
            }
          }
          vis2[e[o].i] = true;
        }
      }

      for(int o = cur.size() - 1; o >= 0; o--) {
        if(cur[o].t <= q[x].t) {
          if(!vis2[cur[o].i]) {
            if(cur[o].w >= w) {
              merge(cur[o].u, cur[o].v);
            }
          }
          vis2[cur[o].i] = true;
        }
      }

      for(int o = l; o <= r; o++) vis2[e[o].i] = false;
    
      ans[idx] = sz[find(u)];
      undo();
    }

    for(int o = l; o <= r; o++) { //update edge with the newest info
      ee[e[o].i].w = e[o].w;
    }
  }
  
  for(int i = 0; i < k; i++) {
    printf("%d\n", ans[i] == 0 ? 1 : ans[i]);
  }
}

int main() {
  int t = 1;
  while(t--) {
    solve();
  }
  return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3876kb

input:

3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2

output:




3
2
3

result:

wrong answer 1st lines differ - expected: '3', found: ''

Subtask #2:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 1274ms
memory: 9956kb

input:

50000 49999
1 2 976392398
2 3 773336157
3 4 849545817
4 5 194340376
5 6 386778507
6 7 40561907
7 8 260116638
8 9 85673124
9 10 149683208
10 11 724746156
11 12 155084527
12 13 416939763
13 14 753621724
14 15 384948880
15 16 625917615
16 17 833747431
17 18 764302034
18 19 4518648
19 20 405679793
20 21...

output:













































































































































































































































































































...

result:

wrong answer 1st lines differ - expected: '7', found: ''

Subtask #3:

score: 0
Wrong Answer

Test #33:

score: 0
Wrong Answer
time: 981ms
memory: 9032kb

input:

32767 32766
1 2 152523690
1 3 736211233
2 4 163158345
2 5 200010458
3 6 902682843
3 7 427399287
4 8 770411775
4 9 322256303
5 10 252775416
5 11 346597970
6 12 297314023
6 13 727299741
7 14 985621564
7 15 101953231
8 16 405434218
8 17 421655547
9 18 817411034
9 19 310455840
10 20 355126049
10 21 7038...

output:


































































































































































































































































































1
1
2
2
6
6...

result:

wrong answer 1st lines differ - expected: '1', found: ''

Subtask #4:

score: 0
Wrong Answer

Test #45:

score: 0
Wrong Answer
time: 945ms
memory: 10824kb

input:

50000 100000
35231 1616 822934828
1668 2202 768458723
26049 41810 238904165
15936 42751 466996423
41068 21425 588205829
29502 11760 732391267
13029 44741 930695124
46168 22085 155239713
9505 43779 638894800
18665 43842 298794735
41763 15511 727702105
7865 27776 53447691
32904 34081 844499614
26327 9...

output:













































































































































































































































































































...

result:

wrong answer 1st lines differ - expected: '2', found: ''

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%