Submission #1298379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298379		nguyenletrung	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	580 KiB

dango_maker

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define ins insert
#define pb push_back
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
int n,m,cnt,ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    vector<string> b(n+1);
    for(int i=1;i<=n;i++){
        string s;cin>>s;
        b[i]=" "+s;
    }
    long long maxNodes = 1LL*m*(n/3) + 1LL*n*(m/3) + 5;
    int MX = (int)maxNodes;
    vector<int> pr(MX+5,0), sz1(MX+5,0), sz2(MX+5,0);
    vector<char> vis(MX+5,0);
    vector<vector<int>> id(n+2, vector<int>(m+2,0));
    auto findp = [&](int u){
        int root = u;
        while(pr[root]!=root) root = pr[root];
        while(u!=root){
            int p = pr[u];
            pr[u]=root;
            u=p;
        }
        return root;
    };
    auto join = [&](int u,int v){
        u = findp(u); v = findp(v);
        if(u==v) return;
        if(sz1[u]+sz2[u] > sz1[v]+sz2[v]) swap(u,v);
        pr[u]=v;
        sz1[v]+=sz1[u];
        sz2[v]+=sz2[u];
    };
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>=3 && b[i][j]=='W' && b[i-1][j]=='G' && b[i-2][j]=='R'){
                cnt++;
                pr[cnt]=cnt;
                sz1[cnt]=1;
                id[i][j]=cnt;
                id[i-1][j]=cnt;
                id[i-2][j]=cnt;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j>=3 && b[i][j]=='W' && b[i][j-1]=='G' && b[i][j-2]=='R'){
                cnt++;
                pr[cnt]=cnt;
                sz2[cnt]=1;
                if(id[i][j]!=0) join(id[i][j],cnt);
                if(id[i][j-1]!=0) join(id[i][j-1],cnt);
                if(id[i][j-2]!=0) join(id[i][j-2],cnt);
            }
        }
    }
    for(int i=1;i<=cnt;i++){
        int r = findp(i);
        if(!vis[r]){
            vis[r]=1;
            ans += max(sz1[r], sz2[r]);
        }
    }
    cout<<ans;
    return 0;
}

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