Submission #3776719


Source Code Expand

#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define ALL(obj) (obj).begin(),(obj).end()

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

template<class T> void corner(bool flg, T hoge) {
	if (flg) {
		cout << hoge << endl;
		exit(0);
	}
	else return;
}

template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {
	o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;
}

template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {
	o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;
}

template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {
	o << "{" << obj.first << ", " << obj.second << "}"; return o;
}

template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

void print(void) {
	cout << endl;
}

template <class Head> void print(Head&& head) {
	cout << head;
	print();
}

template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
	cout << head << " ";
	print(forward<Tail>(tail)...);
}

void YN(bool flg) {
	cout << ((flg) ? "YES" : "NO") << endl;
}

void Yn(bool flg) {
	cout << ((flg) ? "Yes" : "No") << endl;
}

void yn(bool flg) {
	cout << ((flg) ? "yes" : "no") << endl;
}

struct info {
	int to, rev, flg;
};

int main() {
	int N, M; cin >> N >> M;
	string s; cin >> s;
	
	vector<vector<info>> edge(N);
	REP(i,M){
		int a, b; cin >> a >> b;
		a--; b--;
		edge[a].push_back({ b,(int)edge[b].size(),1});
		edge[b].push_back({ a,(int)edge[a].size() - 1,1 });
	}

	V<P<int, int>> ord(N);
	REP(i, N) ord[i] = { 0,i };

	queue<int> q;
	REP(i,N) {
		if (ord[i].first == 0) {
			q.push(i);
			ord[i].first = 1;
		}
		while(q.size()){
			int from = q.front();
			q.pop();
			for(auto u: edge[from]){
				if (ord[u.to].first) continue;
				ord[u.to].first = ord[from].first + 1;
				q.push(u.to);
			}
		}
	}
	sort(ALL(ord));
	
	V<int> node(N, 1);
	REP(n, 100) {
		REP(i, N) {
			if (!node[ord[i].second]) continue;
			int flgA = 0, flgB = 0;
			for (auto u : edge[ord[i].second]) {
				if (u.flg && s[u.to] == 'A') flgA = 1;
				if (u.flg && s[u.to] == 'B') flgB = 1;
			}
			if (flgA && flgB) continue;
			node[ord[i].second] = 0;
			for (auto u : edge[ord[i].second]) {
				u.flg = 0;
				edge[u.to][u.rev].flg = 0;
			}
		}
		REP(i, N) {
			if (!node[ord[N - 1 - i].second]) continue;
			int flgA = 0, flgB = 0;
			for (auto u : edge[ord[N - 1 - i].second]) {
				if (u.flg && s[u.to] == 'A') flgA = 1;
				if (u.flg && s[u.to] == 'B') flgB = 1;
			}
			if (flgA && flgB) continue;
			node[ord[N - 1 - i].second] = 0;
			for (auto u : edge[ord[N - 1 - i].second]) {
				u.flg = 0;
				edge[u.to][u.rev].flg = 0;
			}
		}
	}
	Yn(accumulate(ALL(node), 0)>1);

	return 0;
}

Submission Info

Submission Time
Task C - ABland Yard
User ningenMe
Language C++14 (GCC 5.4.1)
Score 900
Code Size 3884 Byte
Status AC
Exec Time 1093 ms
Memory 14980 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 4
AC × 59
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
sample_04.txt AC 1 ms 256 KB
test_01.txt AC 738 ms 10244 KB
test_02.txt AC 252 ms 10244 KB
test_03.txt AC 149 ms 6144 KB
test_04.txt AC 1058 ms 8704 KB
test_05.txt AC 165 ms 7424 KB
test_06.txt AC 616 ms 6016 KB
test_07.txt AC 73 ms 3328 KB
test_08.txt AC 639 ms 5888 KB
test_09.txt AC 96 ms 4736 KB
test_10.txt AC 60 ms 3328 KB
test_11.txt AC 541 ms 10244 KB
test_12.txt AC 843 ms 12328 KB
test_13.txt AC 133 ms 6144 KB
test_14.txt AC 660 ms 8704 KB
test_15.txt AC 166 ms 7424 KB
test_16.txt AC 311 ms 3328 KB
test_17.txt AC 428 ms 5632 KB
test_18.txt AC 320 ms 4224 KB
test_19.txt AC 558 ms 5760 KB
test_20.txt AC 447 ms 6784 KB
test_21.txt AC 487 ms 5248 KB
test_22.txt AC 222 ms 11268 KB
test_23.txt AC 200 ms 8192 KB
test_24.txt AC 1093 ms 11136 KB
test_25.txt AC 823 ms 8320 KB
test_26.txt AC 469 ms 14340 KB
test_27.txt AC 171 ms 8960 KB
test_28.txt AC 97 ms 6656 KB
test_29.txt AC 691 ms 8960 KB
test_30.txt AC 217 ms 2688 KB
test_31.txt AC 247 ms 12164 KB
test_32.txt AC 176 ms 10116 KB
test_33.txt AC 1032 ms 12032 KB
test_34.txt AC 53 ms 3328 KB
test_35.txt AC 299 ms 14980 KB
test_36.txt AC 1 ms 256 KB
test_37.txt AC 1 ms 256 KB
test_38.txt AC 1 ms 256 KB
test_39.txt AC 1 ms 256 KB
test_40.txt AC 1 ms 256 KB
test_41.txt AC 1 ms 256 KB
test_42.txt AC 1 ms 256 KB
test_43.txt AC 1 ms 256 KB
test_44.txt AC 1 ms 256 KB
test_45.txt AC 1 ms 256 KB
test_46.txt AC 1 ms 256 KB
test_47.txt AC 1 ms 256 KB
test_48.txt AC 1 ms 256 KB
test_49.txt AC 1 ms 256 KB
test_50.txt AC 1 ms 256 KB
test_51.txt AC 1 ms 256 KB
test_52.txt AC 1 ms 256 KB
test_53.txt AC 1 ms 256 KB
test_54.txt AC 1 ms 256 KB
test_55.txt AC 1 ms 256 KB