Submission #1266508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266508		dima2101	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	1 ms	840 KiB

dango_maker

#pragma GCC optimize("O3")
#include <bits/stdc++.h>


struct Edge{
    int stop;
    int flow;
    int capacity;
    int rev;
    Edge(int stop,int flow,int capacity,int rev):stop(stop),flow(flow),capacity(capacity),rev(rev){};
    Edge() = default;
};

const int MAXN = 3001;
int dist[MAXN];
int ptr[MAXN];

bool bfs(int start,int stop,std::vector<std::vector<Edge>>& g){
    for(int i = 0;i < g.size();i++)dist[i] = 1e8;

    dist[start] = 0;
    std::queue<int> q;
    q.push(start);

    while(q.size() > 0){
        int v = q.front();
        q.pop();

        for(auto u:g[v]){
            if(dist[u.stop] > dist[v] + 1 && u.flow != u.capacity){
                dist[u.stop] = dist[v] + 1;
                q.push(u.stop);
            }
        }
    }
    return (dist[stop] < 1e8);
}


int dfs(int v,std::vector<std::vector<Edge>>& g,int stop,int minC = 1e8){
    if(v == stop || minC == 0)return minC;
    for(;ptr[v] < g[v].size();ptr[v]++){
        auto u = g[v][ptr[v]];
        if(dist[u.stop] == dist[v] + 1){
            int flow = dfs(u.stop,g,stop,std::min(u.capacity - u.flow,minC));
            if(flow != 0){
                g[v][ptr[v]].flow += flow;
                g[u.stop][g[v][ptr[v]].rev].flow -= flow;
                return flow;
            }
        }
    }
    return 0;
}

int Dinic(int start,int stop,std::vector<std::vector<Edge>>& g){
    int ans =0 ;
    while(bfs(start,stop,g)){
        for(int i =0 ;i < g.size();i++)ptr[i] = 0;
        int flow = 0;

        do{
            flow = dfs(start,g,stop);
            // std::cout<<flow<<std::endl;
            ans += flow;
        }while(flow != 0);
    }
    return ans;
}


void add_edge(std::vector<std::vector<Edge>>& g,int a,int b){
    g[a].push_back(Edge(b,0,1,g[b].size()));
    g[b].push_back(Edge(a,0,0,g[a].size() - 1));
}

signed
main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n,m;
    std::cin>>n>>m;

    std::vector<std::vector<Edge>> g;
    std::vector<std::vector<char>> a(n,std::vector<char>(m));
    for(int  i=0 ;i < n;i++){
        for(int j =0 ;j < m;j++){
            std::cin>>a[i][j];
        }
    }
    
    std::vector<std::vector<int>> good(n,std::vector<int>(m,-1));
    int cnt =0 ;
    for(int i =0 ;i < n;i++){
        for(int j =0 ;j + 2 < m;j++){
            if(a[i][j] == 'R' && a[i][j+ 1] == 'G' && a[i][j + 2] == 'W'){
                good[i][j] = cnt++;
                g.push_back({});
            }
        }
    }
    int wait = cnt;
    for(int j = 0;j < m;j++){
        for(int i =0 ;i + 2 < n;i++){
            if(a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W'){
                g.push_back({});
                cnt++;
                if(good[i][j] != -1){
                    add_edge(g,good[i][j],cnt - 1);
                }
                if(j >= 1){
                    if(good[i + 1][j - 1] != -1){
                        add_edge(g,good[i+ 1][j - 1],cnt - 1);
                    }
                }
                if(j >= 2){
                    if(good[i + 2][j - 2] != -1){
                        add_edge(g,good[i + 2][j - 2],cnt - 1);
                    }
                }
            }
        }
    }


    g.push_back({});
    g.push_back({});
    for(int i = 0;i < wait;i++){
        add_edge(g,g.size() - 2,i);
    }
    for(int i = wait;i < cnt;i++){
        add_edge(g,i,g.size() - 1);
    }

    assert(cnt <= 1e3);

    std::cout<<cnt - Dinic(g.size() - 2,g.size() - 1,g);

}

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