AtCoder Regular Contest 049

Submission #666609

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
int n;
map<int,set<int> > in;
bool visited[100];
void dfs(int cur){
	if(!in[cur].empty())	return;
	visited[cur]=true;
	for(int i=0;i<n;i++){
		in[i].erase(cur);
	}
	for(int i=0;i<n;i++){
		if(!visited[i]&&in[i].empty())	dfs(i);
	}
}
		
int main(){
	cin>>n;
	int a,b;	cin>>a;
	vector<int> x(a),y(a);
	for(int i=0;i<a;i++){
		cin>>x[i]>>y[i];	x[i]--;	y[i]--;
	}
	cin>>b;
	vector<int> u(b),v(b);
	for(int i=0;i<b;i++){
		cin>>u[i]>>v[i];	u[i]--;	v[i]--;
	}
	int ans=0;
	for(int t=0;t<(int)(1<<b);t++){
		in.clear();
		for(int i=0;i<a;i++)	in[x[i]].insert(y[i]);
		for(int i=0;i<b;i++){
			if(t&(1<<i))	in[v[i]].insert(u[i]);
			else	in[u[i]].insert(-1);
		}
		for(int i=0;i<n;i++)	visited[i]=false;
		for(int i=0;i<n;i++){
			if(in[i].empty()&&!visited[i])	dfs(i);
		}
		int tmp=0;
		for(int i=0;i<n;i++){
			if(in[i].empty())	tmp++;
		}
		ans=max(ans,tmp);
	}
	cout<<ans<<endl;
	return 0;
}

Submission

Task問題 C - ぬりまーす
User nameユーザ名 fiord
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 984 Byte
File nameファイル名
Exec time実行時間 493 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - x_sample_1.txt,x_sample_2.txt,x_sample_3.txt,x_sample_4.txt,x_sample_5.txt
All 100 / 100 corner1.txt,corner2.txt,corner3.txt,corner4.txt,manual1.txt,manual2.txt,manual3.txt,manual4.txt,manual5.txt,random1.txt,random10.txt,random11.txt,random12.txt,random13.txt,random14.txt,random15.txt,random2.txt,random3.txt,random4.txt,random5.txt,random6.txt,random7.txt,random8.txt,random9.txt,x_sample_1.txt,x_sample_2.txt,x_sample_3.txt,x_sample_4.txt,x_sample_5.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
corner1.txt AC 26 ms 256 KB
corner2.txt AC 27 ms 256 KB
corner3.txt AC 4 ms 256 KB
corner4.txt AC 4 ms 256 KB
manual1.txt AC 307 ms 256 KB
manual2.txt AC 488 ms 256 KB
manual3.txt AC 493 ms 256 KB
manual4.txt AC 8 ms 256 KB
manual5.txt AC 9 ms 256 KB
random1.txt AC 130 ms 256 KB
random10.txt AC 79 ms 256 KB
random11.txt AC 37 ms 256 KB
random12.txt AC 66 ms 256 KB
random13.txt AC 52 ms 256 KB
random14.txt AC 115 ms 256 KB
random15.txt AC 58 ms 256 KB
random2.txt AC 62 ms 256 KB
random3.txt AC 65 ms 256 KB
random4.txt AC 151 ms 256 KB
random5.txt AC 305 ms 256 KB
random6.txt AC 122 ms 256 KB
random7.txt AC 77 ms 256 KB
random8.txt AC 351 ms 256 KB
random9.txt AC 313 ms 256 KB
x_sample_1.txt AC 4 ms 256 KB
x_sample_2.txt AC 4 ms 256 KB
x_sample_3.txt AC 4 ms 256 KB
x_sample_4.txt AC 4 ms 256 KB
x_sample_5.txt AC 4 ms 256 KB