Submission #993892


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define pb         push_back

typedef long long ll;
const ll INF = 1000000000ll;
const ll MOD = 1000000007ll;
const double EPS = 1e-8;

bool used[1002];
int n, m;
vector<bool> lang[1000];
int total;

bool dfs(int idx){
	//printf("id: %d\n", idx);
	//cout << total << n << endl;
	if(total == n){
		return true;
	}else{
		for(int j=0; j<n; j++){
			for(int i=0; i<m; i++){
				//printf("%d %d ", j, i);
				//cout << lang[idx][i] << ' ' << lang[j][i] << endl;
				if(used[j] == false && lang[idx][i] == true && lang[j][i] == true){
					used[j] = true;
					total++;
					//printf("%d ok. total=%d\n", j, total);
					if(dfs(j) == true) return true;
					break;
				}
			}
		}
	}
	return false;
}

int main(void) {
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	
	cin >> n >> m;

	for(int i=0; i<n; i++){
		lang[i] = vector<bool>(1000, 0);

		int k;
		cin >> k;
		for(int j=0; j<k; j++){
			int lan;
			cin >> lan;
			lan--;
			lang[i][lan] = true;
		}
	}

	used[0] = true;
	total = 1;
	if(dfs(0)){
		puts("YES");
	}else{
		puts("NO");
	}

	return 0;
}

Submission Info

Submission Time
Task C - Interpretation
User tanutarou
Language C++14 (GCC 5.4.1)
Score 200
Code Size 1171 Byte
Status RE
Exec Time 724 ms
Memory 512 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 0 / 200
Status
AC × 2
AC × 12
AC × 12
RE × 13
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt
dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 256 KB
01-02.txt AC 4 ms 256 KB
01-03.txt AC 4 ms 384 KB
01-04.txt AC 5 ms 384 KB
01-05.txt AC 76 ms 384 KB
01-06.txt AC 265 ms 512 KB
01-07.txt AC 103 ms 384 KB
01-08.txt AC 266 ms 384 KB
01-09.txt AC 159 ms 384 KB
01-10.txt AC 338 ms 500 KB
02-01.txt RE 724 ms 384 KB
02-02.txt RE 110 ms 384 KB
02-03.txt RE 113 ms 512 KB
02-04.txt RE 110 ms 384 KB
02-05.txt RE 111 ms 384 KB
02-06.txt RE 110 ms 384 KB
02-07.txt RE 110 ms 384 KB
02-08.txt RE 110 ms 384 KB
02-09.txt RE 110 ms 384 KB
02-10.txt RE 110 ms 384 KB
02-11.txt RE 109 ms 384 KB
02-12.txt RE 111 ms 384 KB
02-13.txt RE 111 ms 384 KB
sample-01.txt AC 2 ms 256 KB
sample-02.txt AC 2 ms 256 KB