Submission #5442022


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 20;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 60;

ll n,m;
ll s[e5];
graph g;
ll a_cnt[e5];
ll b_cnt[e5];
ll vis[e5];
queue<ll> q;

int main(){
  cin >> n >> m;
  string s_;
  cin >> s_;
  for(ll i = 1;i <= n;i++){
    s[i] = (s_[i-1] == 'A' ? 0 : 1);
  }
  for(ll i = 0;i < m;i++){
    ll a,b;
    cin >> a >> b;
    g[a][b]++;
    g[b][a]++;
    if(s[a] == 0) a_cnt[b]++;
    else b_cnt[b]++;
    if(s[b] == 0) a_cnt[a]++;
    else b_cnt[a]++;
  }
  for(ll i = 1;i <= n;i++){
    if(a_cnt[i] == 0 || b_cnt[i] == 0){
      q.push(i);
      vis[i] = 1;
    }
  }
  // for(ll i = 1;i <= n;i++) cerr << a_cnt[i] << " ";
  // cerr << endl;
  // for(ll i = 1;i <= n;i++) cerr << b_cnt[i] << " ";
  // cerr << endl;
  ll k = n;
  while(!q.empty()){
    ll x = q.front();
    q.pop();
    for(auto y : g[x]){
      if(s[x] == 0) a_cnt[y.first] -= g[x][y.first];
      else b_cnt[y.first] -= g[x][y.first];
      if((a_cnt[y.first] == 0 || b_cnt[y.first] == 0) && vis[y.first] == 0){
        q.push(y.first);
        vis[y.first] = 1;
      }
    }
    k--;
  }
  // for(ll i = 1;i <= n;i++) cerr << a_cnt[i] << " ";
  // cerr << endl;
  // for(ll i = 1;i <= n;i++) cerr << b_cnt[i] << " ";
  // cerr << endl;
  if(k == 0) cout << "No" << endl;
  else cout << "Yes" << endl;


}

Submission Info

Submission Time
Task C - ABland Yard
User deoxy
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1631 Byte
Status
Exec Time 421 ms
Memory 44492 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All 900 / 900 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 2 ms 6400 KB
sample_02.txt 2 ms 6400 KB
sample_03.txt 2 ms 6400 KB
sample_04.txt 2 ms 6400 KB
test_01.txt 296 ms 37452 KB
test_02.txt 331 ms 37580 KB
test_03.txt 160 ms 24484 KB
test_04.txt 224 ms 31012 KB
test_05.txt 180 ms 28324 KB
test_06.txt 151 ms 24356 KB
test_07.txt 88 ms 16012 KB
test_08.txt 136 ms 23332 KB
test_09.txt 125 ms 20388 KB
test_10.txt 65 ms 15756 KB
test_11.txt 307 ms 37452 KB
test_12.txt 288 ms 37580 KB
test_13.txt 136 ms 24484 KB
test_14.txt 241 ms 31908 KB
test_15.txt 216 ms 28324 KB
test_16.txt 101 ms 14464 KB
test_17.txt 133 ms 14080 KB
test_18.txt 122 ms 14848 KB
test_19.txt 189 ms 17536 KB
test_20.txt 137 ms 14080 KB
test_21.txt 146 ms 17920 KB
test_22.txt 306 ms 35496 KB
test_23.txt 206 ms 26660 KB
test_24.txt 283 ms 32420 KB
test_25.txt 230 ms 25356 KB
test_26.txt 421 ms 42572 KB
test_27.txt 203 ms 30628 KB
test_28.txt 105 ms 23076 KB
test_29.txt 248 ms 28068 KB
test_30.txt 60 ms 11904 KB
test_31.txt 271 ms 37708 KB
test_32.txt 219 ms 32588 KB
test_33.txt 348 ms 35236 KB
test_34.txt 64 ms 14476 KB
test_35.txt 366 ms 44492 KB
test_36.txt 2 ms 6400 KB
test_37.txt 3 ms 6400 KB
test_38.txt 2 ms 6400 KB
test_39.txt 2 ms 6400 KB
test_40.txt 3 ms 6400 KB
test_41.txt 2 ms 6400 KB
test_42.txt 2 ms 6400 KB
test_43.txt 2 ms 6400 KB
test_44.txt 2 ms 6400 KB
test_45.txt 2 ms 6400 KB
test_46.txt 2 ms 6400 KB
test_47.txt 2 ms 6400 KB
test_48.txt 3 ms 6400 KB
test_49.txt 3 ms 6400 KB
test_50.txt 2 ms 6400 KB
test_51.txt 2 ms 6400 KB
test_52.txt 2 ms 6400 KB
test_53.txt 2 ms 6400 KB
test_54.txt 2 ms 6400 KB
test_55.txt 2 ms 6400 KB