제출 #196991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
196991		combi1k1	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	243 ms	212572 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;

vector<int> g[N * N];

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)
        return  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')
            t[i][j] = cnt++;
    }

    iota(p,p + cnt,0);
    fill(s,s + cnt,1);

    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < m ; ++j)    if (a[i][j] == 'R') {
        if (a[i + 1][j] == 'G' && a[i + 2][j] == 'W')
            join(t[i][j],t[i + 2][j]);
        if (a[i][j + 1] == 'G' && a[i][j + 2] == 'W')
            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