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
AC × 1
WA × 2
AC × 6
WA × 10
TLE × 4
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