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 |
|
|
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 |