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 |
|
|
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 |