Submission #1284362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284362		WH8	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	485 ms	327680 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
vector<tuple<int,int,int>> hd={{-1,1,1},{0,2,0},{1,1,1},{1,-1,1},{0,-2,0},{-1,-1,1}},
						vd={{-2,0,1},{-1,1,0},{1,1,0},{2,0,1},{1,-1,0},{-1,-1,0}};
signed main(){
	int h,w;cin>>h>>w;
	vector<vector<int>> m(h+2, vector<int>(w+2, 1));
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			char c;cin>>c;
			if(c=='R')m[i][j]=0;
			else if(c=='G')m[i][j]=1;
			else m[i][j]=2;
		}
	}
	vector<vector<array<int, 2>>> v(h+2, vector<array<int,2>>(w+2, array<int,2>{0, 0}));
	vector<vector<int>> al(h*w);
	int nw=1;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(m[i][j]!=1)continue;
			bool hori=false;
			if((m[i][j-1]==0 and m[i][j+1]==2)){
				for (auto [dx,dy,t]:hd){
					int nx=i+dx, ny=j+dy;
					if(nx<=0 or nx>h or ny<=0 or ny>w or !v[nx][ny][t])continue;
					al[nw].pb(v[nx][ny][t]);
					al[v[nx][ny][t]].pb(nw);

				}
				v[i][j][0]=nw;
				hori=true;
				nw++;
				//~ printf("%lld %lld, hori\n",i,j);
			}
			if((m[i-1][j]==0 and m[i+1][j]==2)){
				for (auto [dx,dy,t]:vd){
					int nx=i+dx, ny=j+dy;
					if(nx<=0 or nx>h or ny<=0 or ny>w or !v[nx][ny][t])continue;
					al[nw].pb(v[nx][ny][t]);
					al[v[nx][ny][t]].pb(nw);

				}
				v[i][j][1]=nw;
				if(hori) {
					al[nw].pb(nw-1);
					al[nw-1].pb(nw);
				}
				nw++;
				//~ printf("%lld %lld, vert\n",i,j);
			}
		}
	}
	int N = nw - 1;

// 1) Color the graph to get a bipartition (left/right)
vector<int> part(N + 1, -1);
for (int i = 1; i <= N; ++i) if (part[i] == -1) {
    queue<int> q;
    part[i] = 0; q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : al[u]) {
            if (part[v] == -1) { part[v] = part[u] ^ 1; q.push(v); }
            else { /* if you like, assert(part[v] != part[u]); */ }
        }
    }
}

// 2) Build adjacency from Left->Right only
vector<vector<int>> adj(N + 1);
for (int u = 1; u <= N; ++u) if (part[u] == 0) {
    for (int v : al[u]) if (part[v] == 1) adj[u].push_back(v);
}

// 3) Hopcroft–Karp
vector<int> dist(N + 1, -1), pairU(N + 1, 0), pairV(N + 1, 0);

auto bfs = [&]() -> bool {
    queue<int> q;
    for (int u = 1; u <= N; ++u) {
        if (part[u] == 0 && pairU[u] == 0) { dist[u] = 0; q.push(u); }
        else dist[u] = -1;
    }
    bool found = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            int pu = pairV[v];
            if (pu == 0) found = true;
            else if (dist[pu] == -1) { dist[pu] = dist[u] + 1; q.push(pu); }
        }
    }
    return found;
};

function<bool(int)> dfs2 = [&](int u) -> bool {
    for (int v : adj[u]) {
        int pu = pairV[v];
        if (pu == 0 || (dist[pu] == dist[u] + 1 && dfs2(pu))) {
            pairU[u] = v; pairV[v] = u;
            return true;
        }
    }
    dist[u] = -1;
    return false;
};

int matching = 0;
while (bfs()) {
    for (int u = 1; u <= N; ++u)
        if (part[u] == 0 && pairU[u] == 0 && dfs2(u))
            ++matching;
}

// 4) Answer = #nodes - maximum matching
cout << (N - matching) << '\n';

	//~ vector<int> clr(nw+5, -1);
	//~ array<int,2> sm={0,0};
	//~ auto dfs=[&](auto && dfs, int x, int p)->void{
		//~ sm[p]++;
		//~ for(auto it:al[x]){
			//~ printf("at %lld, going to %lld\n", x, it);
			//~ if(clr[it]!=-1) {
				//~ assert(clr[it]!=clr[x]);
				//~ continue;
			//~ }
			//~ clr[it]=!p;
			//~ dfs(dfs, it, !p);
		//~ }
	//~ };
	//~ int ans=0;
	//~ for(int i=1;i<nw;i++){
		//~ if(clr[i]==-1){
			//~ sm[0]=sm[1]=0;
			//~ clr[i]=0;
			//~ dfs(dfs, i, 0);
			//~ ans+=max(sm[0], sm[1]);
		//~ }
	//~ }
	//~ cout<<ans;
}

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