제출 #889347

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

dango_maker

#include<bits/stdc++.h>
#define MAXN 9000007
using namespace std;

struct edge{
    int to;
    short flow,cap;
    int rev;
};

int n,m;
char t[3007][3007];

vector<edge> v[MAXN];
int s[MAXN],cnt1,cnt2,ans;
int num[3007][3007],num2[3007][3007],total;

int flow,maxflow,source,sink;
int li[MAXN],tim,dist[MAXN],ind[MAXN];
queue<int> q;

void add_edge(int from,int to){
    v[from].push_back({to,0,1,int(v[to].size())});
    v[to].push_back({from,0,0,int(v[from].size())-1});
}

void bfs(int x){
    for(int i=0;i<v[x].size();i++){
        if(li[v[x][i].to]==tim or v[x][i].cap-v[x][i].flow<=0)continue;

        q.push(v[x][i].to);
        li[v[x][i].to]=tim;
        dist[v[x][i].to]=dist[x]+1;
    }
}

void do_bfs(){
    tim++; li[source]=tim;
    while(!q.empty())q.pop();

    q.push(source);

    while(!q.empty()){
        bfs(q.front());
        if(q.front()==sink)return;
        q.pop();
    }
}

int dfs(int x,int mins){
    if(x==sink)return mins;

    if(li[x]!=tim)ind[x]=0;
    li[x]=tim;

    for(int i=ind[x];i<v[x].size();i++){
        if(dist[v[x][i].to]!=dist[x]+1 or v[x][i].cap-v[x][i].flow<=0){
            ind[x]++; continue;
        }

        int curr=dfs(v[x][i].to,1);

        if(curr>0){
            v[x][i].flow+=curr;
            v[v[x][i].to][v[x][i].rev].flow-=curr;
            return curr;
        }

        ind[x]++;
        i=max(i,ind[x]-1);
    }

    return 0;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i=0;i<=n+1;i++){
        for(int f=0;f<=m+1;f++){
            t[i][f]='#';
        }
    }

    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            cin>>t[i][f];
        }
    }

    source=0; sink=n*m;

    total=0;
    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){

            if(t[i][f]=='R' and t[i][f+1]=='G' and t[i][f+2]=='W'){
                total++; num[i][f]=total;
                add_edge(source,total);
            }
            if(t[i][f]=='R' and t[i+1][f]=='G' and t[i+2][f]=='W'){
                total++; num2[i][f]=total;
                add_edge(total,sink);
            }

            if(t[i][f]=='R' and t[i][f+1]=='G' and t[i][f+2]=='W' and t[i+1][f]=='G' and t[i+2][f]=='W'){
                add_edge(num[i][f],num2[i][f]);
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            if(t[i][f]=='G' and t[i][f-1]=='R' and t[i][f+1]=='W' and t[i-1][f]=='R' and t[i+1][f]=='W'){
                add_edge(num[i][f-1],num2[i-1][f]);
            }
        }
    }

    for(int i=2;i<=n;i++){
        for(int f=2;f<=m;f++){
            if(t[i][f]=='W' and t[i][f-2]=='R' and t[i][f-1]=='G' and t[i-2][f]=='R' and t[i-1][f]=='G'){
                add_edge(num[i][f-2],num2[i-2][f]);
            }
        }
    }

    while(true){
        do_bfs();
        if(li[sink]!=tim)break;
        tim++;

        while(true){
            flow=dfs(source,1);
            if(flow==0)break;
            maxflow+=flow;
        }
    }

    cout<<total-maxflow<<"\n";

    return 0;
}

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

dango_maker.cpp: In function 'void bfs(int)':
dango_maker.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
dango_maker.cpp: In function 'int dfs(int, int)':
dango_maker.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=ind[x];i<v[x].size();i++){
      |                      ~^~~~~~~~~~~~

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