Submission #2548059
Source Code Expand
#include<iostream>
#include<iomanip>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<sstream>
using namespace std;
#define P(p) cout<<(p)<<endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort(v.begin(), v.end());
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return
#define lb(v,n) lower_bound(v.begin(),v.end(),n)
#define ub(v,n) upper_bound(v.begin(),v.end(),n)
#define mae(v) max_element(v.begin(),v.end())
#define mie(v) min_element(v.begin(),v.end())
#define INF 0x7FFFFFFF
#define mod 1000000007
typedef long long ll;
////////////////////////////////////////////////////////////
int n;
vector<vector<bool>> f(50,vector<bool>(50,0));
bool ok;
void solve( int now , int cnt , vector<bool> v ){
if( cnt == 0 ){
ok = 1;
ret;
}
if( ok )
ret;
rep(i,0,n){
if( f[now][i] && !v[i] ){
v[i] = 1;
solve(i,cnt-1,v);
v[i] = 0;
}
}
}
int main(){
int m;
cin >> n >> m;
vector<pair<int,int>> e;
rep(i,0,m){
int a,b;
cin >> a >> b;
a--; b--;
f[a][b]=1;
f[b][a]=1;
e.push_back(pair<int,int>(a,b));
}
ll ans = 0;
rep(i,0,m){
rep(j,0,n){
int aa = e[i].first;
int bb = e[i].second;
f[aa][bb] = 0;
f[bb][aa] = 0;
ok = 0;
vector<bool> v(n);
v[i] = 1;
solve( j , n , v );
f[aa][bb] = 1;
f[bb][aa] = 1;
//cout << ok << endl;
if(ok){
ans++;
break;
}
}
}
cout << m - ans << endl;
ret 0;
}
Submission Info
Submission Time |
|
Task |
C - Bridge |
User |
walk_to_work |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1878 Byte |
Status |
WA |
Exec Time |
2103 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
WA |
1 ms |
256 KB |
sample_02.txt |
WA |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_1.txt |
AC |
42 ms |
256 KB |
subtask_1_10.txt |
WA |
7 ms |
256 KB |
subtask_1_11.txt |
WA |
821 ms |
256 KB |
subtask_1_12.txt |
TLE |
2103 ms |
256 KB |
subtask_1_13.txt |
AC |
56 ms |
256 KB |
subtask_1_14.txt |
AC |
56 ms |
256 KB |
subtask_1_15.txt |
WA |
75 ms |
256 KB |
subtask_1_16.txt |
WA |
95 ms |
256 KB |
subtask_1_17.txt |
WA |
95 ms |
256 KB |
subtask_1_2.txt |
WA |
63 ms |
256 KB |
subtask_1_3.txt |
TLE |
2103 ms |
256 KB |
subtask_1_4.txt |
TLE |
2103 ms |
256 KB |
subtask_1_5.txt |
AC |
16 ms |
256 KB |
subtask_1_6.txt |
WA |
478 ms |
256 KB |
subtask_1_7.txt |
AC |
42 ms |
256 KB |
subtask_1_8.txt |
TLE |
2103 ms |
256 KB |
subtask_1_9.txt |
WA |
3 ms |
256 KB |