Submission #117948

#	Time	Username	Problem	Language	Result	Execution time	Memory
117948		JohnTitor	Dango Maker (JOI18_dango_maker)	C++11	13 / 100	3 ms	512 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Dango"
int n, m;
string s[3000];
int id1[3000][3000];
int id2[3000][3000];
int ans=0;
vector <int> w1;
vector <int> w2;
vector <int> r;
int root(int u){
    if(r[u]<0) return u;
    return r[u]=root(r[u]);
}
void unite(int u, int v){
    u=root(u);
    v=root(v);
    if(u==v) return;
    if(r[u]>r[v]) swap(u, v);
    r[u]+=r[v];
    r[v]=u;
    w1[u]+=w1[v];
    w2[u]+=w2[v];
}
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    w1.pb(0);
    w2.pb(0);
    r.pb(0);
    cin>>n>>m;
    FFOR(i, 0, n) cin>>s[i];
    FFOR(i, 0, n){
        FFOR(j, 0, m) if(s[i][j]=='R'){
            if(j+2<m){
                if(s[i][j+1]=='G'&&s[i][j+2]=='W'){
                    id1[i][j]=r.size();
                    r.pb(-1);
                    w1.pb(1);
                    w2.pb(0);
                }
            }
            if(i+2<n){
                if(s[i+1][j]=='G'&&s[i+2][j]=='W'){
                    id2[i][j]=r.size();
                    r.pb(-1);
                    w1.pb(0);
                    w2.pb(1);
                }
            }
        }
    }
//    FFOR(i, 0, n) FFOR(j, 0, m) cerr<<id1[i][j]<<" \n"[j+1==m];
//    cerr<<"\n";
//    FFOR(i, 0, n) FFOR(j, 0, m) cerr<<id2[i][j]<<" \n"[j+1==m];
//    cerr<<"\n";
    FFOR(i, 0, n) FFOR(j, 0, m) if(id2[i][j]){
//        bug(i);
//        bug(j);
//        bug(id1[i][j]);
        if(id1[i][j]) unite(id1[i][j], id2[i][j]);
        if(j) if(id1[i+1][j-1]) unite(id1[i+1][j-1], id2[i][j]);
        if(j>1) if(id1[i+2][j-2]) unite(id1[i+2][j-2], id2[i][j]);
    }
    int ans=0;
    FFOR(i, 1, r.size()) if(i==root(i)){
//        bug(i);
        ans+=max(w1[i], w2[i]);
    }
    writeln(ans);
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:4:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FFOR(i, j, k) for(int i=(j); i<(k); i++)
                                       ^
dango_maker.cpp:85:5: note: in expansion of macro 'FFOR'
     FFOR(i, 1, r.size()) if(i==root(i)){
     ^~~~

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