제출 #66828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
66828		osmanorhan	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	2085 ms	263168 KiB

dango_maker

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset

using namespace std;

typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,char> ic;
typedef pair<db,db> dd;
typedef pair<ii,int> iii;
typedef pair<ii,ii> i4;

const int maxn = 3020;
const int maxm = 3000020;
const int MOd = 1e9 + 7;

int a, b;
int cnt = 0;
char ar[maxn][maxn];
int ex[maxn][maxn][2];
int used[maxm], sz[maxm];
queue<int> q;
vector<int> w[maxm];

void con( int x, int y ) {
	if( x && y ) {
		w[x].pb( y );
		w[y].pb( x );
		sz[x]++;
		sz[y]++;
	}
}

void rem( int n ) {
	used[n] = 1;
	for(int i=0;i<w[n].size();i++) {
		int t = w[n][i];
		sz[t]--;
		if( sz[t] <= 1 ) q.push( t );
	}
}

int main() {

    //freopen("asd.in","r",stdin);
    //freopen("output17.txt","w",stdout);

	scanf("%d %d",&a,&b);

	for(int i=1;i<=a;i++)
		scanf(" %s",ar[i]+1);

	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++) {
			if( ar[i][j] != 'R' ) continue;
			if( j+2 <= b && ar[i][j+1] == 'G' && ar[i][j+2] == 'W' ) ex[i][j][0] = ++cnt;
			if( i+2 <= a && ar[i+1][j] == 'G' && ar[i+2][j] == 'W' ) ex[i][j][1] = ++cnt;
		}

	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++) {
			con( ex[i][j][0], ex[i][j][1] );
			con( ex[i][j][0], ex[i-1][j+1][1] );
			if( i >= 3 ) con( ex[i][j][0], ex[i-2][j+2][1] );
		}
	int ans = 0;
	for(int i=1;i<=cnt;i++)
		if( sz[i] <= 1 ) q.push( i );
	//printf("cnt=%d\n",cnt);
	int last = 1;
	while( last <= cnt ) {
		while( !q.empty() ) {
			int t = q.front();
			q.pop();
			if( used[t] ) continue;
			rem( t );
			ans++;
			for(int i=0;i<w[t].size();i++)
				rem( w[t][i] );
		}
		while( last <= cnt && used[last] ) last++;
		if( last <= cnt ) q.push( last );
	}
	cout << ans << endl;

	return 0;
}

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

dango_maker.cpp: In function 'void rem(int)':
dango_maker.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<w[n].size();i++) {
              ~^~~~~~~~~~~~
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<w[t].size();i++)
                ~^~~~~~~~~~~~
dango_maker.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&a,&b);
  ~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s",ar[i]+1);
   ~~~~~^~~~~~~~~~~~~~~

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