Submission #3222729


Source Code Expand

Copy
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
#include <chrono>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_map>
# include <unordered_set>
using namespace std;
typedef long long ll;
ll max(ll a,ll b){
    if(a>b){
        return a;
    }
    return b;
}
uint32_t rd() {
    uint32_t res;
#ifdef __MINGW32__
    asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
    res = std::random_device()();
#endif
    return res;
}
ll di(ll a, ll b){
    if(a%b==0){
        return a/b;
    }
    return a/b+1;
}
ll i,e,n,m,k,q,a=0,b=0,c=0,j=0,x,y,z,w,mi=1001010,mx=-1,sum=0,f=0,l,r,hi,lo;
int main(){
    ios::sync_with_stdio(false);
    map<pair<ll,ll>,ll> ed;
    string s;
    cin>>n>>m;
    vector<vector<ll>> v(n);
    v.clear();
    ll v2[n];
    for(i=0;i<n;i++){
        v2[i]=0;
    }
    vector<vector<ll>> v4(n);
    v4.clear();
    cin>>s;
    for(i=0;i<m;i++){
        cin>>x>>y;
        x--;
        y--;
        v[x].push_back(y);
        v[y].push_back(x);
        if(s[x]==s[y]){
            if(x==y){
                v2[x]++;
                ed[{x,y}]=sum;
                sum++;
                v4[x].push_back(y);
            }
            else{
                v2[x]++;
                v2[y]++;
                ed[{x,y}]=sum;
                ed[{y,x}]=sum;
                sum++;
                v4[x].push_back(y);
                v4[y].push_back(x);
            }
        }
    }
    for(i=0;i<n;i++){
        for(e=0;e<v[i].size();e++){
            x=i;
            y=v[i][e];
            if(s[x]!=s[y]){
                c+=v2[x]*v2[y];
            }
        }
    }
    if(c>m){
        cout<<"Berrr";
        return 0;
    }
    vector<vector<ll>> v3(sum);
    for(i=0;i<n;i++){
        for(e=0;e<v[i].size();e++){
            x=i;
            y=v[i][e];
            if(s[x]!=s[y]){
                for(a=0;a<v4[x].size();a++){
                    for(b=0;b<v4[y].size();b++){
                        z=ed[{x,v4[x][a]}];
                        w=ed[{y,v4[y][b]}];
                        v3[z].push_back(w);
                        v3[w].push_back(z);
                    }
                }
            }
        }
    }
    vector<ll> dfs;
    bool tr[sum];
    for(i=0;i<sum;i++){
        tr[i]=false;
    }
    ll cn=0;
    for(i=0;i<sum;i++){
        if(tr[i]==false){
            cn++;
            dfs.resize(0);
            tr[i]=true;
            j=0;
            dfs.push_back(i);
            while(dfs.size()>j){
                x=dfs[j];
                for(e=0;e<v3[x].size();e++){
                    if(tr[v3[x][e]]==false){
                        dfs.push_back(v3[x][e]);
                        tr[v3[x][e]]=true;
                    }
                }
                j++;
            }
        }
    }
    if(c>sum-cn){
        cout<<"Yes";
        return 0;
    }
    cout<<"No";
}

Submission Info

Submission Time
Task C - ABland Yard
User NCT
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3444 Byte
Status
Exec Time 321 ms
Memory 40908 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 0 / 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 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB
test_01.txt 140 ms 26960 KB
test_02.txt 139 ms 27088 KB
test_03.txt 128 ms 20092 KB
test_04.txt 107 ms 22864 KB
test_05.txt 164 ms 24396 KB
test_06.txt 72 ms 15872 KB
test_07.txt 62 ms 10880 KB
test_08.txt 71 ms 15488 KB
test_09.txt 54 ms 12160 KB
test_10.txt 61 ms 10752 KB
test_11.txt 141 ms 26960 KB
test_12.txt 138 ms 27088 KB
test_13.txt 129 ms 20092 KB
test_14.txt 113 ms 22864 KB
test_15.txt 162 ms 24396 KB
test_16.txt 63 ms 8960 KB
test_17.txt 82 ms 11648 KB
test_18.txt 65 ms 9728 KB
test_19.txt 114 ms 13952 KB
test_20.txt 85 ms 12800 KB
test_21.txt 84 ms 12160 KB
test_22.txt 135 ms 24912 KB
test_23.txt 96 ms 18048 KB
test_24.txt 181 ms 25344 KB
test_25.txt 132 ms 19072 KB
test_26.txt 210 ms 32080 KB
test_27.txt 116 ms 21584 KB
test_28.txt 48 ms 13648 KB
test_29.txt 127 ms 20480 KB
test_30.txt 37 ms 5888 KB
test_31.txt 211 ms 31948 KB
test_32.txt 125 ms 23120 KB
test_33.txt 194 ms 27472 KB
test_34.txt 42 ms 8192 KB
test_35.txt 321 ms 40908 KB
test_36.txt 1 ms 256 KB
test_37.txt 1 ms 256 KB
test_38.txt 1 ms 256 KB
test_39.txt 1 ms 256 KB
test_40.txt 1 ms 256 KB
test_41.txt 1 ms 256 KB
test_42.txt 1 ms 256 KB
test_43.txt 1 ms 256 KB
test_44.txt 1 ms 256 KB
test_45.txt 1 ms 256 KB
test_46.txt 1 ms 256 KB
test_47.txt 1 ms 256 KB
test_48.txt 1 ms 256 KB
test_49.txt 1 ms 256 KB
test_50.txt 1 ms 256 KB
test_51.txt 1 ms 256 KB
test_52.txt 1 ms 256 KB
test_53.txt 1 ms 256 KB
test_54.txt 1 ms 256 KB
test_55.txt 1 ms 256 KB