제출 #164510

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

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i<b; i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i = n-1; i>=0; i--)
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define pb push_back
#ifdef BALBIT
#define IOS()
#define bug(x) cerr<<__LINE__<<' '<<#x<<": "<<x<<endl
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(x)
#endif
 
const ll mod = 1e9+7;
const int maxn = 3e3+5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;
 
int mx[maxn*maxn/3],my[maxn*maxn/3];
bool vy[maxn*maxn/3];
vector<int> edge[maxn*maxn/3];
vector<int>id; 
clock_t stT;
 
int N, M;
int greedy_matching()
{
    int c = 0;
    for (int x=0; x<N; ++x) {
    	int at = id[x];
        if (mx[at] == -1) {
            for (auto y : edge[at]) {
                if (my[y] == -1) {
                        mx[at] = y; my[y] = at;
                        c++;
                        break;
                }
            }
        }
    }
    return c;
}
 
bool DFS(int x)
{
    for (auto y : edge[x]) {
        if (!vy[y]) {
            vy[y] = true;
            if (my[y] == -1 || DFS(my[y]))
            {
                mx[x] = y; my[y] = x;
                return true;
            }
        }
    }
    return false;
}
 
int bipartite_matching()
{
    memset(mx, -1, sizeof(mx));
    memset(my, -1, sizeof(my));
 	REP(i,N) id.pb(i); random_shuffle (ALL(id));
    int c = greedy_matching();
 
    for (int x=0; x<N; ++x){
    	if (mx[id[x]] == -1)  
        {
            fill(vy, vy+M, 0);
            if (DFS(id[x])) c++;
            if(clock()- stT >= CLOCKS_PER_SEC * 1.9) return c; 
        }
	}
        
    return c;
}
 
char grd[maxn][maxn];
 
int idup[maxn][maxn];
int idrt[maxn][maxn];
 
 
signed main(){
	IOS();
	srand(time(0));
	stT = clock();
	int n, m; cin>>n>>m;
//	assert(n!=3000 || m!=3000);
	REP(i,n) REP(j,m) cin>>grd[i][j];
	int nup = 0, nrt = 0;
	memset(idup, -1, sizeof(idup));
	memset(idrt, -1, sizeof(idrt));
	REP(i,n)REP(j,m){
 
		if(grd[i][j]=='G'){
			if (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' ) {
				idup[i][j] = nup++;
			}
			if (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' ) {
				idrt[i][j] = nrt ++;
			}
		}
	}
 
	N = nup; M = nrt;
//	Dinic dd (N,S,T);
	REP(i,n) REP(j,m){
		if(idup[i][j]!=-1){
//			cout<<i<<' '<<j<<' '<<idup[i][j]<<endl;
 
			if(idrt[i][j] != -1) {
				edge[idup[i][j]].pb(idrt[i][j]);
			}
			if(i && idrt[i-1][j+1]!=-1){
				edge[idup[i][j]].pb(idrt[i-1][j+1]);
			}
			if(j && idrt[i+1][j-1]!=-1){
				edge[idup[i][j]].pb(idrt[i+1][j-1]);
			}
		}
 
	}
	cout<<nup + nrt - bipartite_matching() << endl;
	
}

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

dango_maker.cpp: In function 'int bipartite_matching()':
dango_maker.cpp:7:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i,a,b) for (int i = a; i<b; i++)
                    ^
dango_maker.cpp:8:18: note: in expansion of macro 'FOR'
 #define REP(i,n) FOR(i,0,n)
                  ^~~
dango_maker.cpp:73:3: note: in expansion of macro 'REP'
   REP(i,N) id.pb(i); random_shuffle (ALL(id));
   ^~~
dango_maker.cpp:73:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   REP(i,N) id.pb(i); random_shuffle (ALL(id));
                      ^~~~~~~~~~~~~~

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