oj.uz

답안 #568797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
568797 2022-05-26T08:18:20 Z almothana05 다리 (APIO19_bridges) C++14
27 / 100
 215 ms 24860 KB 
#include<bits/stdc++.h>
#define mod 1000000007
#define inf 10000000000000000
using namespace std;
vector<vector<int> >mst , q;
pair<int , int>f[200000];
vector<vector<int> >edge;
vector<pair<int , int> >gr[100000];
int erg[200000] ,vis[100000] , erge;
void dfs(int x , int cmp){
   // cout << x << ' ' << erg << "\n";
   vis[x] = 1;
   erge++;
   for(int i = 0 ; i < gr[x].size() ; i++){
      int kind = gr[x][i].first , val = gr[x][i].second;
      // cout << x << ' ' << kind << ' ' << val << "\n";
      if(vis[kind] == 0 && val >= cmp){
         dfs(kind , cmp);
      }
   }
}

int fater(int x){
   if(x == f[x].first){
      return x;
   }
   f[x].first = fater(f[x].first);
   return f[x].first;
}
void merge(int z , int x , int y){
  while(q.size() && q[q.size() - 1][0] > z){
     erg[q[q.size() - 1][2]] = f[fater(q[q.size() - 1][1])].second;
     q.pop_back();
  } 
  if(fater(x) != fater(y)){
     f[fater(x)].second += f[fater(y)].second;
     f[fater(y)].first = fater(x);
  }
}
int main(){
   for(int i = 0 ; i < 200000 ; i++){
      f[i] = {i , 1};
   }
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   int menge , numm , nummer , ed , cmp , comp ;;
   cin >> menge >> ed;

   for(int i = 0 ; i < ed ; i++){
      cin >> numm >> nummer >> cmp;
      mst.push_back({cmp , numm , nummer}); 
      gr[numm].push_back({nummer , cmp});
      gr[nummer].push_back({numm , cmp});
      edge.push_back({numm , gr[numm].size() - 1 , nummer , gr[nummer].size() - 1});
   }
   sort(mst.begin() , mst.end());
    
   int que ;
   cin >> que;
   if(menge <= 1000 && que <= 10000 && ed <= 1000){
      while(que--){
      // cout << "ja\n";
      cin >> numm;
      if(numm == 1){
         cin >> numm >> nummer;
         numm--;
         gr[edge[numm][0]][edge[numm][1]].second = nummer;
         gr[edge[numm][2]][edge[numm][3]].second = nummer;
         // cout << *edge[numm].first << "\n";
         // for(int i = 0 ; i < gr[1].size() ; i++){
            // cout << gr[1][i].second << ' ';
         // }
         // cout << "\n";
      }
      else{
         cin >> numm >> nummer;
          erge = 0;
         dfs(numm , nummer);
         cout << erge << "\n";
         for(int i = 0 ; i <= menge ; i++){
            vis[i] = 0;
         }
      }
   }
      return 0;
   }
   for(int i = 0 ; i < que ; i++){
      cin >> cmp >> numm >> nummer;
      q.push_back({nummer , numm , i});
   }
   sort(q.begin() , q.end());

   for(int i = ed - 1; i >= 0 ; i--){
      merge(mst[i][0] , mst[i][1] , mst[i][2]);
   }
   while(q.size() ){
     erg[q[q.size() - 1][2]] = f[fater(q[q.size() - 1][1])].second;
     q.pop_back();
  } 
   for(int i = 0 ; i < que ; i++){
      cout << erg[i] << "\n";
   }
}

Compilation message

bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |    for(int i = 0 ; i < gr[x].size() ; i++){
      |                    ~~^~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:54:46: warning: narrowing conversion of '(gr[numm].std::vector<std::pair<int, int> >::size() - 1)' from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   54 |       edge.push_back({numm , gr[numm].size() - 1 , nummer , gr[nummer].size() - 1});
      |                              ~~~~~~~~~~~~~~~~^~~
bridges.cpp:54:46: warning: narrowing conversion of '(gr[numm].std::vector<std::pair<int, int> >::size() - 1)' from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
bridges.cpp:54:79: warning: narrowing conversion of '(gr[nummer].std::vector<std::pair<int, int> >::size() - 1)' from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   54 |       edge.push_back({numm , gr[numm].size() - 1 , nummer , gr[nummer].size() - 1});
      |                                                             ~~~~~~~~~~~~~~~~~~^~~
bridges.cpp:54:79: warning: narrowing conversion of '(gr[nummer].std::vector<std::pair<int, int> >::size() - 1)' from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
bridges.cpp:46:43: warning: unused variable 'comp' [-Wunused-variable]
   46 |    int menge , numm , nummer , ed , cmp , comp ;;
      |                                           ^~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 60 ms 4384 KB Output is correct
4 Correct 6 ms 4180 KB Output is correct
5 Correct 8 ms 4180 KB Output is correct
6 Correct 7 ms 4268 KB Output is correct
7 Correct 6 ms 4180 KB Output is correct
8 Correct 7 ms 4268 KB Output is correct
9 Correct 9 ms 4308 KB Output is correct
10 Correct 7 ms 4180 KB Output is correct
11 Correct 6 ms 4264 KB Output is correct
12 Correct 6 ms 4180 KB Output is correct
13 Correct 8 ms 4280 KB Output is correct
14 Correct 8 ms 4180 KB Output is correct
15 Correct 9 ms 4180 KB Output is correct
16 Correct 7 ms 4180 KB Output is correct
17 Correct 7 ms 4180 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 17.0

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

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 24724 KB Output is correct
2 Correct 53 ms 10232 KB Output is correct
3 Correct 76 ms 17772 KB Output is correct
4 Correct 100 ms 17776 KB Output is correct
5 Correct 215 ms 24744 KB Output is correct
6 Correct 157 ms 24712 KB Output is correct
7 Correct 152 ms 24796 KB Output is correct
8 Correct 136 ms 17292 KB Output is correct
9 Correct 96 ms 17372 KB Output is correct
10 Correct 97 ms 17448 KB Output is correct
11 Correct 121 ms 21400 KB Output is correct
12 Correct 130 ms 21396 KB Output is correct
13 Correct 149 ms 21580 KB Output is correct
14 Correct 186 ms 24860 KB Output is correct
15 Correct 164 ms 24800 KB Output is correct
16 Correct 167 ms 24148 KB Output is correct
17 Correct 185 ms 24096 KB Output is correct
18 Correct 177 ms 24220 KB Output is correct
19 Correct 150 ms 24204 KB Output is correct
20 Correct 140 ms 22536 KB Output is correct
21 Correct 184 ms 22572 KB Output is correct
22 Correct 148 ms 23844 KB Output is correct
23 Correct 127 ms 21976 KB Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct
3 Correct 60 ms 4384 KB Output is correct
4 Correct 6 ms 4180 KB Output is correct
5 Correct 8 ms 4180 KB Output is correct
6 Correct 7 ms 4268 KB Output is correct
7 Correct 6 ms 4180 KB Output is correct
8 Correct 7 ms 4268 KB Output is correct
9 Correct 9 ms 4308 KB Output is correct
10 Correct 7 ms 4180 KB Output is correct
11 Correct 6 ms 4264 KB Output is correct
12 Correct 6 ms 4180 KB Output is correct
13 Correct 8 ms 4280 KB Output is correct
14 Correct 8 ms 4180 KB Output is correct
15 Correct 9 ms 4180 KB Output is correct
16 Correct 7 ms 4180 KB Output is correct
17 Correct 7 ms 4180 KB Output is correct
18 Incorrect 116 ms 17372 KB Output isn't correct
19 Halted 0 ms 0 KB -