QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#883835 | #5063. Fillomino | Larunatrecy | TL | 3ms | 30288kb | C++14 | 4.7kb | 2025-02-05 19:17:56 | 2025-02-05 19:18:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
x=(f?-x:x);
}
const int N = 550;
const int M = N*N;
int vis[M],dep[M];
int gmin(int x,int y){if(!x||!y)return x+y;return dep[x]<dep[y]?x:y;}
vector<int> lst[M];
int fa[M],deg[M],low[M];
vector<int> G[M];
void dfs(int x)
{
vis[x]=1;
low[x]=0;
for(int y:G[x])if(!vis[y])
{
dep[y]=dep[x]+1;
dfs(y);
low[x]=gmin(low[x],low[y]);
deg[x]++;
fa[y]=x;
}
else if(dep[y]<dep[x])
{
low[x]=gmin(low[x],y);
}
}
int used[M],perm[M],seq[M],pos[M];
int test=0,ot=0,cnt=0;
void dfs2(int x)
{
perm[++cnt]=x;pos[x]=cnt;
vis[x]=1;
for(int y:lst[x])if(!vis[y])dfs2(y);
}
void solve(int n,int s,int t)
{
for(int i=1;i<=n;i++)lst[i].clear(),fa[i]=deg[i]=dep[i]=vis[i]=0;
dep[1]=0;
dfs(s);
queue<int> q;
for(int i=1;i<=n;i++)vis[i]=0;
int c=0;
int u=t;while(u)vis[u]=1,seq[++c]=u,u=fa[u];
for(int i=1;i<=n;i++)
if(i!=t&°[i]==0)q.push(i);
while(!q.empty())
{
int x=q.front();
q.pop();
lst[fa[x]].push_back(x);
lst[low[x]].push_back(x);
deg[fa[x]]--;
if(!deg[fa[x]]&&!vis[fa[x]])q.push(fa[x]);
}
for(int i=1;i<=n;i++)used[i]=perm[i]=0;
cnt=0;
for(int i=c;i>=1;i--)
{
int u=seq[i];
dfs2(u);
}
}
int a[N][N],b[N][N],id[N][N],idx=0;
int n,m;
inline int roln(int x){return (x%n+n)%n;}
inline int rolm(int y){return (y%m+m)%m;}
struct node
{
int tp,x,y;
};
bool operator <(node a,node b)
{
return a.tp<b.tp;
}
int dX=0,dY=0;
int nxt[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int get(int x,int y)
{
int H=0,C=0;
for(int k=0;k<4;k++)
{
int dx=roln(x+nxt[k][0]);
int dy=rolm(y+nxt[k][1]);
if(a[dx][dy]!=1)
C++,H|=(1<<k);
}
if(C==1)return 3;
if(C==2&&H!=3&&H!=12)return 2;
return 1;
}
void solve()
{
int C1,C2,C3,x1,y1,x2,y2,x3,y3;
read(n);read(m);
read(C1);read(C2);read(C3);
read(x1);read(y1);read(x2);read(y2);read(x3);read(y3);
x1--;y1--;x2--;y2--;x3--;y3--;
char A='A',B='B',C='C';
if(C1>C2)swap(C1,C2),swap(x1,x2),swap(y1,y2),swap(A,B);
if(C1>C3)swap(C1,C3),swap(x1,x3),swap(y1,y3),swap(A,C);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
a[i][j]=0;
a[x1][y1]=1;a[x2][y2]=2;a[x3][y3]=3;
bool flag=0;
dX=x1;dY=y1;
x1=roln(x1-dX);y1=rolm(y1-dY);
x2=roln(x2-dX);y2=rolm(y2-dY);
x3=roln(x3-dX);y3=rolm(y3-dY);
if(x2>x3)swap(x2,x3),swap(y2,y3),swap(B,C),swap(C2,C3);
int cur=C1;
auto chk = [&](int c,int p)
{
if(flag)return;
if(c==1)
{
if(p==x2||p==x3)return;
flag=1;
for(int j=0,q=y1;j<m;j++,q=rolm(q+1))
{
cur--;
if(!a[p][q])a[p][q]=5;
if(!cur)break;
}
}
else
{
if(p==y2||p==y3)return;
flag=1;
for(int i=0,q=x1;i<n;i++,q=roln(q+1))
{
cur--;
if(!a[q][p])a[q][p]=5;
if(!cur)break;
}
}
};
if(cur)
{
for(int i=x2;i<=x3;i++)a[i][y2]=4;
for(int i=min(y2,y3);i<=max(y2,y3);i++)a[x3][i]=4;
a[x2][y2]=2;a[x3][y3]=3;
for(int x=x1-1;x<=x1+1;x++)chk(1,roln(x));
for(int y=y1-1;y<=y1+1;y++)chk(2,rolm(y));
// for(int i=0;i<n;i++)
// {
//
// for(int j=0;j<m;j++)
// {
// cout<<a[i][j];
// }
// cout<<endl;
// }
// cout<<endl;
priority_queue<node>Q;
for(int i=0;i<n;i++)for(int j=0;j<m;j++)
if(a[i][j]==5)a[i][j]=0,Q.push({4,i,j});
cur=C1;a[0][0]=0;Q.push({5,0,0});
while(cur)
{
auto u=Q.top();
Q.pop();
int x=u.x,y=u.y;
if(a[x][y])continue;
a[x][y]=1;
cur--;
for(int k=0;k<4;k++)
{
int dx=roln(x+nxt[k][0]);
int dy=rolm(y+nxt[k][1]);
if(a[dx][dy])continue;
Q.push({get(dx,dy),dx,dy});
}
}
}
// for(int i=0;i<n;i++)
// {
//
// for(int j=0;j<m;j++)
// {
// cout<<a[i][j];
// }
// cout<<endl;
// }
idx=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(a[i][j]!=1)id[i][j]=++idx;
else id[i][j]=0;
for(int i=1;i<=idx;i++)G[i].clear();
for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(id[i][j])
{
for(int k=0;k<4;k++)
{
int x=roln(i+nxt[k][0]);
int y=rolm(j+nxt[k][1]);
if(id[x][y])
G[id[i][j]].push_back(id[x][y]);
}
}
solve(idx,id[x2][y2],id[x3][y3]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(id[i][j])
{
if(pos[id[i][j]]<=C2)a[i][j]=2;
else a[i][j]=3;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
int x=roln(i-dX);
int y=rolm(j-dY);
if(a[x][y]==1)putchar(A);
else if(a[x][y]==2)putchar(B);
else putchar(C);
}
putchar('\n');
}
}
int main()
{
int T;
read(T);
while(T--)
{
solve();
}
return 0;
}
/*
5
10 10
33 33 34
1 1 9 9 4 6
*/
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 30288kb
input:
2 3 3 1 3 5 1 1 2 2 3 3 4 4 5 5 6 2 2 2 3 3 3
output:
ACC BBC BCC AAAA BABB BCCC BCCC
result:
ok ok (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
100000 3 3 2 1 6 3 3 1 2 2 2 3 3 7 1 1 3 1 1 1 2 3 3 3 1 7 1 1 1 3 1 1 3 3 3 2 1 6 3 3 1 3 1 1 3 3 7 1 1 2 1 3 2 1 1 3 3 3 2 4 2 2 2 1 1 2 3 3 3 2 4 3 3 1 1 2 1 3 3 2 4 3 2 1 1 2 1 3 3 3 3 5 1 1 2 3 1 2 2 3 3 2 4 3 1 1 2 1 2 3 3 3 1 5 3 3 3 2 2 1 2 3 3 5 1 3 2 1 1 2 2 2 3 3 3 5 1 2 1 2 3 3 2 3 3 7 1...