比赛 |
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;
}