Submission #116021

#	Time	Username	Problem	Language	Result	Execution time	Memory
116021		oolimry	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	2060 ms	11124 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;
vector<int> vis, match;
vector<int> adj[200000];

int Aug(int u){
    if(vis[u]) return 0;
    vis[u] = 1;
    for(int j = 0;j < adj[u].size();j++){
        int r = adj[u][j];
        if(match[r] == -1 || Aug(match[r])){
            match[r] = u;
            return 1;
        }
    }
    return 0;
}
int main()
{
    //freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int rows, cols;
    cin >> rows >> cols;

    int arr[rows][cols];
    for(int r = 0;r < rows;r++){
        string s;
        cin >> s;
        for(int c = 0;c < cols;c++){
            if(s[c] == 'R') arr[r][c] = 0;
            else if(s[c] == 'G') arr[r][c] = 1;
            else arr[r][c] = 2;
        }
    }

    typedef pair<int,int> ii;
    vector<ii> ver;
    vector<ii> hor;
    for(int r = 0;r < rows;r++){
        for(int c = 0;c < cols - 2;c++){
            if(arr[r][c] == 0 && arr[r][c+1] == 1 && arr[r][c+2] == 2){
                hor.push_back(ii(r,c));
            }
        }
    }

    for(int r = 0;r < rows - 2;r++){
        for(int c = 0;c < cols;c++){
            if(arr[r][c] == 0 && arr[r+1][c] == 1 && arr[r+2][c] == 2){
                ver.push_back(ii(r,c));
            }
        }
    }

    int n = ver.size();
    int m = hor.size();
    int V = n + m;
    //cout << ver[0].first << " " << ver[0].second << "\n";
    //cout << hor[1].first << " " << hor[1].second << "\n";
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            set<ii> nodes;
            ii x = hor[j];
            nodes.insert(x);
            x.second++;
            nodes.insert(x);
            x.second++;
            nodes.insert(x);
            x.second++;

            ii y = ver[i];
            nodes.insert(y);
            y.first++;
            nodes.insert(y);
            y.first++;
            nodes.insert(y);
            y.first++;

            if(nodes.size() != 6){
                adj[i].push_back(j+n);
                //cout << i << " " << j << "\n";
            }
        }
    }

    int MCBM = 0;
    match.assign(V,-1);
    for(int i = 0;i < n;i++){
        vis.assign(n,0);
        MCBM += Aug(i);
    }
    cout << V - MCBM;
    return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int Aug(int)':
dango_maker.cpp:10:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0;j < adj[u].size();j++){
                   ~~^~~~~~~~~~~~~~~

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