제출 #153436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153436		mhy908	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	465 ms	262148 KiB

dango_maker

#include <bits/stdc++.h>
#define pb push_back
#define INF 987654321
using namespace std;
typedef long long LL;
int n, m, x;
char str[3010][3010];
int col[3010][3010][3], ans;
short int re[3010][3010];
vector<int> link[3500010], id;
int par[3300010];
bool used[3300010];
int dist[3300010];
int A[3300010], B[3300010];
vector<vector<int> > vc;
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)
{
    queue<int> Q;
    for(int i=0; i<vc[p].size(); i++){
        if(!used[vc[p][i]]){
            dist[vc[p][i]]=0;
            Q.push(vc[p][i]);
        }
        else dist[vc[p][i]]=INF;
    }
    while(!Q.empty()){
        int a=Q.front();
        Q.pop();
        for(int b: link[a]){
            if(B[b]!=-1&&dist[B[b]]==INF){
                dist[B[b]]=dist[a]+1;
                Q.push(B[b]);
            }
        }
    }
}
bool dfs(int a){
    for(int b: link[a]){
        if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(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[vc[p][i]] && dfs(vc[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++){
        scanf("%s", str[i]+1);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(str[i][j]=='R'&&str[i][j+1]=='G'&&str[i][j+2]=='W'){
                ++x;
                col[i][j][++re[i][j]]=x;
                col[i][j+1][++re[i][j+1]]=x;
                col[i][j+2][++re[i][j+2]]=x;
            }
            if(str[i][j]=='R'&&str[i+1][j]=='G'&&str[i+2][j]=='W'){
                ++x;
                col[i][j][++re[i][j]]=x;
                col[i+1][j][++re[i+1][j]]=x;
                col[i+2][j][++re[i+2][j]]=x;
            }
        }
    }
    if(x>=3300000){
        while(1){
            x++;
        }
    }
    for(int i=1; i<=x; i++)par[i]=i;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(re[i][j]==2){
                mergepar(col[i][j][1], col[i][j][2]);
                link[col[i][j][1]].pb(col[i][j][2]);
                link[col[i][j][2]].pb(col[i][j][1]);
            }
        }
    }
    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.resize(0);
    vc.resize(maxpar);
    for(int i=1; i<=x; i++){
        vc[par[i]].pb(i);
    }
    fill(A+1, A+x+1, -1);
    fill(B+1, B+x+1, -1);
    for(int i=0; i<maxpar; i++){
        if(vc[i].size()==1)ans++;
        else ans+=vc[i].size()-hopcroft_carp(i);
    }
    printf("%d", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'void bfs(int)':
dango_maker.cpp:30: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)':
dango_maker.cpp:50:43: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if(B[b]==-1||dist[B[b]]==dist[a]+1&&dfs(B[b])){
                      ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
dango_maker.cpp: In function 'int hopcroft_carp(int)':
dango_maker.cpp:65: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:74: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:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", str[i]+1);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67