oj.uz

답안 #719560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719560 2023-04-06T09:43:58 Z keisuke6 다리 (APIO19_bridges) C++17
27 / 100
 845 ms 70152 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool f(vector<int> S){
  for(int x:S)if(x==1) return false;
  return true;
}
struct Unionfind{
  vector<int> par, siz;
  //初期化
  Unionfind(int n) : par(n,-1) , siz(n,1) {}
  int root(int x) {
    if(par[x] == -1) return x;
    else return par[x] = root(par[x]);
  }
  bool issame(int x,int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y){
    x = root(x); y = root(y);
    if(x ==  y) return false;
    if(siz[x] < siz[y]) swap(x,y);
    par[y] =  x;
    siz[x] += siz[y];
    return  true;
  }
  int size(int x) {
    return siz[root(x)];
  }
};
signed main(){
  int N,M,Q;
  cin>>N>>M;
  vector<vector<int>> G(N);
  unordered_map<int,int> m;
  map<int,multiset<int>> s;
  map<int,pair<int,int>> ed;
  map<int,int> edc;
  for(int i=0;i<M;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;
    b--;
    ed[i] = {a,b};
    edc[i] = c;
    m[a*N+b] = max(c,m[a*N+b]);
    m[b*N+a] = max(c,m[a*N+b]);
    s[a*N+b].insert(c);
    s[b*N+a].insert(c);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  cin>>Q;
  vector<int> T(Q),A(Q),B(Q);
  for(int i=0;i<Q;i++){
    cin>>T[i]>>A[i]>>B[i];
    A[i]--;
  }
  if(f(T)){
    Unionfind uf(N);
    vector<pair<int,int>> S(Q);
    for(int i=0;i<Q;i++) S[i] = {B[i],A[i]};
    map<int,int> ans;
    sort(S.rbegin(),S.rend());
    vector<tuple<int,int,int>> C = {};
    for(int i=0;i<N;i++)for(int j:G[i]){
      C.push_back({m[i*N+j],i,j});
    }
    sort(C.rbegin(),C.rend());
    int ind = 0;
    for(int i=0;i<Q;i++){
      while(ind != 2*(int)(m.size())){
        int a,b,c;
        tie(a,b,c) = C[ind];
        if(a < S[i].first) break;
        uf.unite(b,c);
        ind++;
      }
      ans[S[i].first*N+S[i].second] = uf.size(S[i].second);
    }
    for(int i=0;i<Q;i++) cout<<ans[B[i]*N+A[i]]<<endl;
    return 0;
  }
  if(max({N,M,Q}) <= 10000){
    for(int i=0;i<Q;i++){
      if(T[i] == 1){
        int a,b;
        tie(a,b) = ed[A[i]];
        s[a*N+b].erase(s[a*N+b].find(edc[A[i]]));
        s[a*N+b].insert(B[i]);
        swap(a,b);
        s[a*N+b].erase(s[a*N+b].find(edc[A[i]]));
        s[a*N+b].insert(B[i]);
        edc[A[i]] = B[i];
        continue;
      }
      queue<int> q;
      q.push(A[i]);
      vector<bool> seen(N,false);
      seen[A[i]] = true;
      while(!q.empty()){
        int pos = q.front();
        q.pop();
        for(int x:G[pos]){
          if(seen[x] || *s[pos*N+x].rbegin() < B[i]) continue;
          seen[x] = true;
          q.push(x);
        }
      }
      int count = 0;
      for(int i=0;i<N;i++) count += seen[i];
      cout<<count<<endl;
    }
    return 0;
  }
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 138 ms 1096 KB Output is correct
4 Correct 22 ms 1476 KB Output is correct
5 Correct 23 ms 696 KB Output is correct
6 Correct 25 ms 724 KB Output is correct
7 Correct 27 ms 668 KB Output is correct
8 Correct 24 ms 740 KB Output is correct
9 Correct 31 ms 740 KB Output is correct
10 Correct 21 ms 692 KB Output is correct
11 Correct 22 ms 724 KB Output is correct
12 Correct 21 ms 696 KB Output is correct
13 Correct 31 ms 724 KB Output is correct
14 Correct 27 ms 848 KB Output is correct
15 Correct 31 ms 852 KB Output is correct
16 Correct 25 ms 660 KB Output is correct
17 Correct 23 ms 744 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 30992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 173 ms 21528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 792 ms 70152 KB Output is correct
2 Correct 268 ms 10668 KB Output is correct
3 Correct 436 ms 59748 KB Output is correct
4 Correct 437 ms 59788 KB Output is correct
5 Correct 791 ms 68840 KB Output is correct
6 Correct 811 ms 70076 KB Output is correct
7 Correct 822 ms 68712 KB Output is correct
8 Correct 552 ms 41504 KB Output is correct
9 Correct 517 ms 41328 KB Output is correct
10 Correct 480 ms 41484 KB Output is correct
11 Correct 678 ms 55160 KB Output is correct
12 Correct 634 ms 55244 KB Output is correct
13 Correct 640 ms 55356 KB Output is correct
14 Correct 742 ms 67768 KB Output is correct
15 Correct 767 ms 68352 KB Output is correct
16 Correct 829 ms 69076 KB Output is correct
17 Correct 845 ms 69048 KB Output is correct
18 Correct 789 ms 69364 KB Output is correct
19 Correct 782 ms 69356 KB Output is correct
20 Correct 655 ms 59728 KB Output is correct
21 Correct 697 ms 59688 KB Output is correct
22 Correct 767 ms 67252 KB Output is correct
23 Correct 657 ms 56088 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 30992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 138 ms 1096 KB Output is correct
4 Correct 22 ms 1476 KB Output is correct
5 Correct 23 ms 696 KB Output is correct
6 Correct 25 ms 724 KB Output is correct
7 Correct 27 ms 668 KB Output is correct
8 Correct 24 ms 740 KB Output is correct
9 Correct 31 ms 740 KB Output is correct
10 Correct 21 ms 692 KB Output is correct
11 Correct 22 ms 724 KB Output is correct
12 Correct 21 ms 696 KB Output is correct
13 Correct 31 ms 724 KB Output is correct
14 Correct 27 ms 848 KB Output is correct
15 Correct 31 ms 852 KB Output is correct
16 Correct 25 ms 660 KB Output is correct
17 Correct 23 ms 744 KB Output is correct
18 Incorrect 219 ms 30992 KB Output isn't correct
19 Halted 0 ms 0 KB -