Submission #8872743


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define INF 1e10
#define MOD 1e9+7
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
struct Union{
  vector<int> par;
   Union(int a){
   par=vector<int>(a,-1);
   }
   int find(int a){
     if(par[a]<0)
       return a;
     else
       return par[a]=find(par[a]);
   }
   bool same(int a,int b){
    return find(a)==find(b);
   }
   int Size(int a){
     return -par[find(a)];
   }
   void unite(int a,int b){
     a=find(a);
     b=find(b);
     if(a==b)
       return;
   if(Size(b)>Size(a))
      swap<int>(a,b);
    par[a]+=par[b];
     par[b]=a;
   }
 
  int much(int a){
  vector<int> e(a);
   rep(i,a){
   e[i]=find(i);
    }
   sort(all(e)); 
   e.erase(unique(all(e)),e.end());
   return e.size();
   }
 };
signed main(){
int a,b;
  cin>>a>>b;
  vector<int> c(b),d(b);
  rep(i,b)
    cin>>c[i]>>d[i];
  int f=0;
  rep(j,b){
  Union e(a);
  rep(i,b){
    if(i==j)
      continue;
    else
    e.unite(c[i]-1,d[i]-1);
 }
    if(e.much(a)>1)
      f++;
  }
  cout<<f;
}

Submission Info

Submission Time
Task C - Bridge
User Matatabi
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1507 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 20
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_1.txt AC 1 ms 256 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 1 ms 256 KB
subtask_1_12.txt AC 1 ms 256 KB
subtask_1_13.txt AC 1 ms 256 KB
subtask_1_14.txt AC 1 ms 256 KB
subtask_1_15.txt AC 1 ms 256 KB
subtask_1_16.txt AC 1 ms 256 KB
subtask_1_17.txt AC 1 ms 256 KB
subtask_1_2.txt AC 1 ms 256 KB
subtask_1_3.txt AC 1 ms 256 KB
subtask_1_4.txt AC 1 ms 256 KB
subtask_1_5.txt AC 1 ms 256 KB
subtask_1_6.txt AC 1 ms 256 KB
subtask_1_7.txt AC 1 ms 256 KB
subtask_1_8.txt AC 1 ms 256 KB
subtask_1_9.txt AC 1 ms 256 KB