Submission #3202578
Source Code Expand
/** * File : C.cpp * Author : Kazune Takahashi * Created : 2018-9-15 21:34:24 * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <functional> #include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725)); #include <chrono> // std::chrono::system_clock::time_point start_time, end_time; // start = std::chrono::system_clock::now(); // double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count(); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; // const ll M = 1000000007; int N, M; string s; int L[200010]; set<int> S[200010][2]; bool ok[200010]; int main() { cin >> N >> M >> s; for (auto i = 0; i < N; i++) { if (s[i] == 'A') { L[i] = 0; } else { L[i] = 1; } } for (auto i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; S[b][L[a]].insert(a); S[a][L[b]].insert(b); } fill(ok, ok + N, true); queue<int> Q; for (auto i = 0; i < N; i++) { // cerr << "S[" << i << "][0] = " << (int)S[i][0].empty() << endl; // cerr << "S[" << i << "][1] = " << (int)S[i][1].empty() << endl; if (S[i][0].empty() || S[i][1].empty()) { Q.push(i); } } while (!Q.empty()) { int now = Q.front(); Q.pop(); if (!ok[now]) { continue; } ok[now] = false; for (auto k = 0; k < 2; k++) { if (S[now][k].empty()) { continue; } for (auto x : S[now][k]) { S[x][L[now]].erase(now); if (S[x][L[now]].empty()) { Q.push(x); } } } } bool first[2] = {false, false}; for (auto i = 0; i < N; i++) { if (ok[i]) { first[L[i]] = true; } } if (first[0] && first[1]) { cout << "Yes" << endl; } else { cout << "No" << endl; } }
Submission Info
Submission Time | |
---|---|
Task | C - ABland Yard |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 2568 Byte |
Status | AC |
Exec Time | 247 ms |
Memory | 38532 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
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 | 8 ms | 18944 KB |
sample_02.txt | AC | 8 ms | 18944 KB |
sample_03.txt | AC | 8 ms | 18944 KB |
sample_04.txt | AC | 8 ms | 18944 KB |
test_01.txt | AC | 156 ms | 33668 KB |
test_02.txt | AC | 167 ms | 33796 KB |
test_03.txt | AC | 103 ms | 27648 KB |
test_04.txt | AC | 147 ms | 31488 KB |
test_05.txt | AC | 120 ms | 29696 KB |
test_06.txt | AC | 95 ms | 27648 KB |
test_07.txt | AC | 52 ms | 23680 KB |
test_08.txt | AC | 90 ms | 27392 KB |
test_09.txt | AC | 74 ms | 25600 KB |
test_10.txt | AC | 51 ms | 23552 KB |
test_11.txt | AC | 156 ms | 33668 KB |
test_12.txt | AC | 152 ms | 33796 KB |
test_13.txt | AC | 97 ms | 27648 KB |
test_14.txt | AC | 142 ms | 31488 KB |
test_15.txt | AC | 130 ms | 29696 KB |
test_16.txt | AC | 104 ms | 27520 KB |
test_17.txt | AC | 137 ms | 27776 KB |
test_18.txt | AC | 107 ms | 27648 KB |
test_19.txt | AC | 187 ms | 31872 KB |
test_20.txt | AC | 140 ms | 27776 KB |
test_21.txt | AC | 101 ms | 28800 KB |
test_22.txt | AC | 175 ms | 33540 KB |
test_23.txt | AC | 126 ms | 29696 KB |
test_24.txt | AC | 215 ms | 36864 KB |
test_25.txt | AC | 166 ms | 33152 KB |
test_26.txt | AC | 247 ms | 38532 KB |
test_27.txt | AC | 117 ms | 28928 KB |
test_28.txt | AC | 58 ms | 24320 KB |
test_29.txt | AC | 159 ms | 32384 KB |
test_30.txt | AC | 48 ms | 23552 KB |
test_31.txt | AC | 175 ms | 33924 KB |
test_32.txt | AC | 117 ms | 29316 KB |
test_33.txt | AC | 229 ms | 37248 KB |
test_34.txt | AC | 45 ms | 22784 KB |
test_35.txt | AC | 240 ms | 38276 KB |
test_36.txt | AC | 8 ms | 19072 KB |
test_37.txt | AC | 8 ms | 19072 KB |
test_38.txt | AC | 8 ms | 18944 KB |
test_39.txt | AC | 8 ms | 19072 KB |
test_40.txt | AC | 8 ms | 19072 KB |
test_41.txt | AC | 8 ms | 18944 KB |
test_42.txt | AC | 8 ms | 19072 KB |
test_43.txt | AC | 8 ms | 19072 KB |
test_44.txt | AC | 7 ms | 19072 KB |
test_45.txt | AC | 8 ms | 19072 KB |
test_46.txt | AC | 8 ms | 19072 KB |
test_47.txt | AC | 8 ms | 19072 KB |
test_48.txt | AC | 8 ms | 19072 KB |
test_49.txt | AC | 8 ms | 18944 KB |
test_50.txt | AC | 8 ms | 18944 KB |
test_51.txt | AC | 8 ms | 18944 KB |
test_52.txt | AC | 8 ms | 19072 KB |
test_53.txt | AC | 8 ms | 19072 KB |
test_54.txt | AC | 8 ms | 19072 KB |
test_55.txt | AC | 7 ms | 19072 KB |