Submission #153556

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
153556	2019-09-14T15:39:11 Z	mhy908	Dango Maker (JOI18_dango_maker)	C++17	Compilation error	0 ms	0 KB

dango_maker

#include <bits/stdc++.h>
#define pb push_back
#define INF 987654321
using namespace std;
typedef long long LL;
int n, m, x;
vector<char> str[3010];
int ans;
vector<int> id;
vector<int> par;
vector<bool> used;
vector<int> dist, A, B;
vector<vector<int> > vc, link;
vector<vector<vector<int> > >col;
unordered_map<int, int> mp;
queue<int> Q;
LL opop[200000000];
LL op5op[200000000];
LL op3op[200000000];
LL op2op[200000000];
LL o2pop[200000000];
int findpar(int num)
{
    if(num==par[num])return num;
    return par[num]=findpar(par[num]);
}
void mergepar(int a, int b)
{
    a=findpar(a);
    b=findpar(b);
    par[a]=par[b];
}
void bfs(int p)
{
    for(int i=0; i<vc[p].size(); i++){
        if(!used[i]){
            dist[i]=0;
            Q.push(i);
        }
        else dist[i]=INF;
    }
    while(!Q.empty()){
        int a=Q.front();
        Q.pop();
        for(int b: link[vc[p][a]]){
            b=mp[b];
            if(B[b]!=-1&&dist[B[b]]==INF){
                dist[B[b]]=dist[a]+1;
                Q.push(B[b]);
            }
        }
    }
}
bool dfs(int p, int a){
    for(int b: link[vc[p][a]]){
        b=mp[b];
        if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(p, B[b])){
            used[a]=true;
            A[a]=b;
            B[b]=a;
            return true;
        }
    }
    return false;
}
int hopcroft_carp(int p)
{
    int match=0;
    while(1){
        bfs(p);
        int flow=0;
        for(int i=0; i<vc[p].size(); i++)
            if(!used[i]&&dfs(p, i))flow++;
        if(!flow)break;
        match+=flow;
    }
    return match/2;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        str[i].pb(0);
        for(int j=1; j<=m; j++){
            char y;
            scanf(" %c", &y);
            str[i].pb(y);
        }
    }
    col.resize(n+1);
    for(int i=1; i<=n; i++)col[i].resize(m+1);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(j+2<=m)
                if(str[i][j]=='R'&&str[i][j+1]=='G'&&str[i][j+2]=='W'){
                    ++x;
                    col[i][j].pb(x);
                    col[i][j+1].pb(x);
                    col[i][j+2].pb(x);
                }
            if(i+2<=n)
                if(str[i][j]=='R'&&str[i+1][j]=='G'&&str[i+2][j]=='W'){
                    ++x;
                    col[i][j].pb(x);
                    col[i+1][j].pb(x);
                    col[i+2][j].pb(x);
                }
        }
    }
    if(x>3000000)while(1){}
    for(int i=1; i<=n; i++){
        str[i].clear();
        vector<char>().swap(str[i]);
    }
    link.resize(x+1);
    for(int i=1; i<=x; i++)link[i].resize(3, -1);
    for(int i=0; i<=x; i++)par.pb(i);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(col[i][j].size()==2){
                mergepar(col[i][j][1], col[i][j][0]);
                if(link[col[i][j][1]][0]==-1)link[col[i][j][1]][0]=col[i][j][0];
                else if(link[col[i][j][1]][1]==-1)link[col[i][j][1]][1]=col[i][j][0];
                else if(link[col[i][j][1]][2]==-1)link[col[i][j][1]][2]=col[i][j][0];
                if(link[col[i][j][0]][0]==-1)link[col[i][j][0]][0]=col[i][j][1];
                else if(link[col[i][j][0]][1]==-1)link[col[i][j][0]][1]=col[i][j][1];
                else if(link[col[i][j][0]][2]==-1)link[col[i][j][0]][2]=col[i][j][1];
            }
        }
    }
    col.clear();
    vector<vector<vector<int> > >().swap(col);
    for(int i=1; i<=x; i++){
        id.pb(findpar(i));
    }
    sort(id.begin(), id.end());
    id.erase(unique(id.begin(), id.end()), id.end());
    int maxpar=1;
    for(int i=1; i<=x; i++){
        par[i]=lower_bound(id.begin(), id.end(), par[i])-id.begin();
        maxpar=max(maxpar, par[i]+1);
    }
    id.clear();
    vector<int>().swap(id);
    vc.resize(maxpar);
    for(int i=1; i<=x; i++){
        vc[par[i]].pb(i);
    }
    par.clear();
    vector<int>().swap(par);
    for(int i=0; i<maxpar; i++){
        if(vc[i].size()==1)ans++;
        else{
            for(int j=0; j<vc[i].size(); j++)mp[vc[i][j]]=j;
            used.resize(vc[i].size()+2);
            dist.resize(vc[i].size()+2);
            A.resize(vc[i].size()+2);
            B.resize(vc[i].size()+2);
            for(int j=0; j<A.size(); j++)A[j]=B[j]=-1;
            ans+=vc[i].size()-hopcroft_carp(i);
            mp.clear();
            dist.clear();
            A.clear();
            B.clear();
            used.clear();
            vector<int>().swap(dist);
            vector<int>().swap(A);
            vector<int>().swap(B);
            vector<bool>().swap(used);
        }
    }
    printf("%d", ans);
}

Compilation message

dango_maker.cpp: In function 'void bfs(int)':
dango_maker.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vc[p].size(); i++){
                  ~^~~~~~~~~~~~~
dango_maker.cpp: In function 'bool dfs(int, int)':
dango_maker.cpp:57:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(p, B[b])){
dango_maker.cpp: In function 'int hopcroft_carp(int)':
dango_maker.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<vc[p].size(); i++)
                      ~^~~~~~~~~~~~~
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:154:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<vc[i].size(); j++)mp[vc[i][j]]=j;
                          ~^~~~~~~~~~~~~
dango_maker.cpp:159:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<A.size(); j++)A[j]=B[j]=-1;
                          ~^~~~~~~~~
dango_maker.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &y);
             ~~~~~^~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<wchar_t>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIwEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<char>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIcEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa1): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x24f): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa9): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x114): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x294): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status