QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#851104#8355. T3kkkgjyismine4Compile Error//C++203.4kb2025-01-10 15:21:552025-01-10 15:21:56

Judging History

你现在查看的是最新测评结果

  • [2025-01-10 15:21:56]
  • 评测
  • [2025-01-10 15:21:55]
  • 提交

answer

#include<bits/stdc++.h>
#define K 305
#define N 100005
#define M 1000005
using namespace std;
int n;
int h[N],to[M],nxt[M],w[M],cnt;
void jb(int u,int v,int W){
	to[++cnt]=v;
	w[cnt]=W;
	nxt[cnt]=h[u];
	h[u]=cnt;
}
void JB(int u,int v,int W){
	jb(u,v,W);
	jb(v,u,0); 
}
int s,t,k,dis[N],ct[N];
int dfs(int u,int fl){
	if(u==t) return fl;
	int dl=0;
	for(int i=h[u];i!=0;i=nxt[i]){
		int v=to[i];
		if(w[i]&&dis[u]==dis[v]+1){
			int tmp=dfs(v,min(w[i],fl-dl));
			w[i]-=tmp;w[i^1]+=tmp;
			dl+=tmp;
			if(fl==dl) return dl;
		}
	}
	ct[dis[u]]--;
	if(ct[dis[u]]==0) dis[s]=k+1;
	ct[++dis[u]]++;
	return dl;
}
int work(){
	int res=0;
	while(dis[s]<=k) res+=dfs(s,n*n);
	return res;
}
int id[K][K],tot,ty[K][K];
int a[4][K],c[2][K];
int pos[4][K],vis[K][K];
bool run(){
	bool flag=0;
	for(int i=1;i<=n&&!flag;i++){
		if(a[0][i]==0) continue;
		while(pos[0][i]<=n&&vis[pos[0][i]][i]) pos[0][i]++;
		if(pos[0][i]<=n&&ty[pos[0][i]][i]==0){
			flag=1;
			vis[pos[0][i]][i]=1;
			a[0][i]--;
			printf("U%d\n",i);
		}
	}
	for(int i=1;i<=n&&!flag;i++){
		if(a[1][i]==0) continue;
		while(pos[1][i]>=1&&vis[pos[1][i]][i]) pos[1][i]--;
		if(pos[1][i]>=1&&ty[pos[1][i]][i]==0){
			flag=1;
			vis[pos[1][i]][i]=1;
			a[1][i]--;
			printf("D%d\n",i);
		}
	}
	for(int i=1;i<=n&&!flag;i++){
		if(a[2][i]==0) continue;
		while(pos[2][i]<=n&&vis[i][pos[2][i]]) pos[2][i]++;
		if(pos[2][i]<=n&&ty[i][pos[2][i]]==1){
			flag=1;
			vis[i][pos[2][i]]=1;
			a[2][i]--;
			printf("L%d\n",i);
		}
	}
	for(int i=1;i<=n&&!flag;i++){
		if(a[3][i]==0) continue;
		while(pos[3][i]>=1&&vis[i][pos[3][i]]) pos[3][i]--;
		if(pos[3][i]>=1&&ty[i][pos[3][i]]==1){
			flag=1;
			vis[i][pos[3][i]]=1;
			a[3][i]--;
			printf("R%d\n",i);
		}
	}
	return flag;
}
int vs[K*2];
vector<int > vec[K*2];
bool ys(int x,int y){
	if(pos[0][y]==x&&a[0][y]>0) return 1;
	if(pos[1][y]==x&&a[1][y]>0) return 1;
	if(pos[2][x]==y&&a[2][y]>0) return 1;
	if(pos[3][x]==y&&a[3][y]>0) return 1;
	return 0;
}
bool find(int u,int z){
	vs[u]=2;
	for(int v:vec[u]){
		if(u==z&&!ys(u,v-n)) continue;
		if(!vs[v]){
			ty[min(u,v)][max(u,v)-n]^=1;
			if(find(v,z)) return 1;
			ty[min(u,v)][max(u,v)-n]^=1;
		}
		else if(v==z){
			ty[min(u,v)][max(u,v)-n]^=1;
			return 1;
		}
	}
	vs[u]=1;
	return 0;
}
int main(){
	cnt=1;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) id[i][j]=++tot;
	k=t=tot+n*2+2;s=k-1;
	for(int i=0;i<4;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]),c[i/2][j]+=a[i][j];
	for(int i=1;i<=n;i++){
		JB(s,tot+i,c[0][i]);
		JB(s,tot+n+i,c[1][i]);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			JB(id[i][j],t,1);
			JB(tot+j,id[i][j],1);
			JB(tot+n+i,id[i][j],1);
		}
	if(work()!=n*n){
		puts("NO");
		return 0;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			int u=id[i][j];
			for(int e=h[u];e!=0;e=nxt[e]){
				int v=to[e];
				if(w[e]&&v>tot){
					if(v>tot+n) ty[i][j]=1;
					break;
				}
			}
		}
	for(int i=1;i<=n;i++) pos[1][i]=pos[3][i]=n,pos[0][i]=pos[2][i]=1;
	do{
		for(int i=1;i<=2*n;i++) vec[i].clear(),vs[i]=0;
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(!vis[i][j]){
						if(ty[i][j]==1) vec[i].push_back(j+n);
						else vec[j+n].push_back(i);
					}
		int fl=0;
		for(int i=1;i<=n;i++)
			if(!vs[i]) fl|=find(i,i);
	}while(fl);
	for(int d=1;d<=n*n;d++)run();
	return 0;
}

詳細信息

answer.code: In function ‘int main()’:
answer.code:160:16: error: ‘fl’ was not declared in this scope
  160 |         }while(fl);
      |                ^~
answer.code:116:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
answer.code:122:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  122 |                         scanf("%d",&a[i][j]),c[i/2][j]+=a[i][j];
      |                         ~~~~~^~~~~~~~~~~~~~~