CODE FESTIVAL 2016 Final

Submission #992608

Source codeソースコード

#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
//#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1)/*v1の後ろにv2を入れる*/)
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;
	vector<unordered_set<int>>lang_graph(M);
	vector<int>speaker_num(M);
	rep(i, N) {
		int K;
		cin >> K;
		vector<int>lang_list(K);
		rep(j, K)cin >> lang_list[j];
		rep(j, K)lang_list[j]--;//0-origin
		rep(j, K)speaker_num[lang_list[j]]++;
		rep(j, K - 1) {
			//lang_list[j]とlang_list[x]を話せる人がいるので辺を引く
			lang_graph[lang_list[j]].insert(lang_list[j + 1]);
		}
	}

	//通訳を2人以上挟んでもいいと解釈して解く
	vector<int>searched(M);
	stack<int>dfs;
	rep(i, M)if (speaker_num[i]) { dfs.push(i); break; }
	while (!dfs.empty()) {
		auto x = dfs.top(); dfs.pop();
		if (searched[x])continue;
		searched[x] = 1;
		for (auto y : lang_graph[x]) {
			dfs.push(y);
		}
	}
	rep(i, M)if (searched[i] == 0 && speaker_num[i]) {
		cout << "NO" << endl;
		return 0;
	}

	cout << "YES" << endl;



}

Submission

Task問題 C - Interpretation
User nameユーザ名 Ubiquitin
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 2115 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 0 / 200 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 0 / 200 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 3 ms 256 KB
01-02.txt WA
01-03.txt AC 3 ms 384 KB
01-04.txt AC 3 ms 256 KB
01-05.txt AC 3 ms 256 KB
01-06.txt WA
01-07.txt WA
01-08.txt AC 3 ms 384 KB
01-09.txt WA
01-10.txt AC 3 ms 384 KB
02-01.txt WA
02-02.txt AC 18 ms 512 KB
02-03.txt AC 41 ms 8576 KB
02-04.txt WA
02-05.txt WA
02-06.txt AC 36 ms 9728 KB
02-07.txt WA
02-08.txt AC 16 ms 256 KB
02-09.txt AC 28 ms 7296 KB
02-10.txt WA
02-11.txt AC 28 ms 6912 KB
02-12.txt WA
02-13.txt AC 30 ms 6656 KB
sample-01.txt WA
sample-02.txt AC 3 ms 256 KB