比赛 4043级NOIP2022欢乐赛1st 评测结果 AAAAAAAAAA
题目名称 Multiplayer Moo 最终得分 100
用户昵称 ムラサメ 运行时间 0.370 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-10-28 22:29:52
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int maxn = 62505;
int q,n,cnt[maxn],size = 1,first[maxn];
int color[maxn],num;
int a[255][255];
int vis[255][255];
int used[maxn];
bool usededge[maxn<<2];
int ans = 0,tot;
int dx[5] = {0,0,1,-1};
int dy[5] = {1,-1,0,0};
struct Edge{
    int v,nt;
}edge[maxn << 2];
struct Node{
    int x,y;
};
template<class T>inline void read(T&x){
    x = 0;char ch = getchar();bool flag = 0;
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x <<3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
}
template<class T>void putch(const T x){
    if(x > 9) putch(x / 10);
    putchar(x % 10 | 48); 
} 
template<class T>void put(const T x){
    if(x < 0) putchar('-'),putch(-x);
    else putch(x);
}
void readdata(){
    read(n);
    for(int i = 1;i <= n; ++ i)
        for(int j = 1;j <= n; ++ j)
            read(a[i][j]);
}
void eadd(int u,int v){
    edge[++size].v = v;
    edge[size].nt = first[u];
    first[u] = size;
}
void bfs1(int sx,int sy){
    ++tot;
    color[tot] = a[sx][sy];
    queue<Node>q;
    q.push((Node){sx,sy});
    vis[sx][sy] = tot;
    while(!q.empty()){
        Node u = q.front();
        q.pop();
        cnt[tot]++;
        for(int i = 0;i < 4; ++ i){
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            
            if(nx <= 0 || ny <= 0 || nx > n || ny > n) continue;
            if(!vis[nx][ny] && a[nx][ny] == a[sx][sy]){
                q.push((Node){nx,ny});
                vis[nx][ny] = tot;
                continue;
            } 
            
            if(vis[nx][ny] && vis[nx][ny] < tot){
                eadd(tot,vis[nx][ny]); 
                eadd(vis[nx][ny],tot);
            }
        }
    }
    ans = max(ans,cnt[tot]);
}

void bfs2(int s1,int s2){
    queue<int>q;
    num++;
    int tmp = 0;
    q.push(s2);
    q.push(s1);
    used[s1] = num;
    used[s2] = num;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        tmp += cnt[u];
        for(int i = first[u];i;i = edge[i].nt){
            int v = edge[i].v;
            if(used[v] == num || v < s1) continue;
            if(color[v]!=color[s1] && color[v]!=color[s2]) continue;
            if(usededge[i]) return;
            usededge[i] = 1;usededge[i^1] = 1;
            used[v] = num;
            q.push(v);
        } 
    }
    ans=max(ans,tmp);
}
void work(){
    for(int i = 1;i <= n; ++ i)
        for(int j = 1;j <= n; ++ j){
            if(!vis[i][j]) bfs1(i,j);
        }
    put(ans);puts("");
    ans = 0;
    int maxans = (n*n)>>1;
    for(int i = 1;i <= tot; ++ i){
        for(int j = first[i];j;j = edge[j].nt){
            int v = edge[j].v;
            if(v <= i) continue;
            if(color[v] == color[i]) continue;
            if(usededge[j]) continue;
            usededge[j] = 1;usededge[j^1] = 1;
            bfs2(i,v);
            if(ans > maxans) break;
        }
    }
    put(ans);
} 
int main(){
	freopen("multimoo_silver_18open.in","r",stdin);
	freopen("multimoo_silver_18open.out","w",stdout);
    readdata();
    work();
    return 0;
}