제출 #196993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
196993		combi1k1	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	3 ms	404 KiB

dango_maker

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define ld  double

#define sz(x)   (int)x.size()
#define all(x)  x.begin(),x.end()

#define pb  emplace_back
#define X   first
#define Y   second

const int   N   = 3005;

typedef pair<int,int>   ii;

char a[N][N];
int  t[N][N];

int p[N * N];
int s[N * N];

int lead(int x) {
    return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y)   {
    x = lead(x);
    y = lead(y);

    if (x == y)
        assert(0);
    if (s[x] < s[y])
        swap(x,y);

    p[y] = x;
    s[x] += s[y];

    return  1;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int m;  cin >> m;

    int cnt = 0;

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    {
        cin >> a[i][j];

        if (a[i][j] != 'G') {
            p[cnt] = cnt;
            s[cnt] = 1;

            t[i][j] = cnt++;
        }
        if (a[i][j] == 'W') {
            if (i > 1 && a[i - 1][j] == 'G' && a[i - 2][j] == 'R')
                join(t[i][j],t[i - 2][j]);
            if (j > 1 && a[i][j - 1] == 'G' && a[i][j - 2] == 'R')
                join(t[i][j],t[i][j - 2]);
        }
    }

    int ans = 0;

    for(int i = 0 ; i < cnt ; ++i)  if (p[i] == i)
        ans += s[i] / 2;

    cout << ans << endl;
}

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