QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#609652#9412. Stop the Castleucup-team902#WA 2ms11292kbC++173.7kb2024-10-04 13:38:502024-10-04 13:38:54

Judging History

This is the latest submission verdict.

  • [2024-10-04 13:38:54]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 11292kb
  • [2024-10-04 13:38:50]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define ll long long
#define pii pair<ll,ll>
#define gc getchar
#define fi first
#define se second
#define bg begin

template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}

inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
cs int N=100005;
int n,m;
int str,des,tot;
struct edge{
	int v,cap,r;
	edge(int a=0,int b=0,int c=0):v(a),cap(b),r(c){}
};
vector<edge> e[N];
inline void addedge(int u,int v,int w){
	e[u].pb(edge(v,w,e[v].size()));
	e[v].pb(edge(u,0,e[u].size()-1));
}
#define It vector<edge>::iterator
namespace Flow{
	int lev[N];It tp[N];
	queue<int> q;
	inline bool bfs(){
		memset(lev,-1,sizeof(int)*(tot+1));
		lev[str]=0,q.push(str);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(edge &x:e[u]){
				if(lev[x.v]==-1&&x.cap>0){
					lev[x.v]=lev[u]+1,q.push(x.v);
				}
			}
		}
		return lev[des]!=-1;
	}
	int dfs(int u,int flow){
		if(u==des)return flow;
		int res=0;
		for(It &it=tp[u];it!=e[u].end();it++){
			if(lev[it->v]==lev[u]+1&&it->cap>0){
				int now=dfs(it->v,min(it->cap,flow-res));
				res+=now,it->cap-=now,e[it->v][it->r].cap+=now;
				if(res==flow)break;
			}
		}
		return res;
	}
	inline int dinic(){
		int res=0;
		while(bfs()){
			for(int i=1;i<=tot;i++)tp[i]=e[i].bg();
			res+=dfs(str,1e9);
		}
		return res;
	}
}
int r[N],c[N],cntx,cnty;
int r2[N],c2[N];
void clear(){
	for(int i=0;i<=tot;i++)e[i].clear();
	str=des=tot=0;
}
struct node{
	int t,l,r;
	node(int _t=0,int _l=0,int _r=0):t(_t),l(_l),r(_r){}
}lix[N],liy[N];
int inter(node x,node y){
	return y.l<=x.t&&x.t<=y.r&&x.l<=y.t&&y.t<=x.r;
}
void solve(){
	n=read();cntx=cnty=0;
	for(int i=1;i<=n;i++)r[i]=read(),c[i]=read();			
	m=read();
	for(int i=1;i<=m;i++)r2[i]=read(),c2[i]=read();
	tot=0,str=++tot,des=++tot;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)if(i!=j&&r[i]==r[j]&&c[i]<c[j]){
		if(c[i]+1==c[j]){
			puts("-1");
			clear();
			return;
		}	
		int ok=0;
		for(int k=1;k<=m;k++)if(r2[k]==r[i]&&c[i]<c2[k]&&c2[k]<c[j]){
			ok=1;
		}
		if(ok)continue;
		//cout<<i<<" "<<j<<'\n';
	//	cout<<r[i]<<" "<<c[i]+1<<" "<<c[j]-1<<'\n';
		lix[++cntx]=node(r[i],c[i]+1,c[j]-1);
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)if(i!=j&&c[i]==c[j]&&r[i]<r[j]){
		if(r[i]+1==r[j]){
			puts("-1");
			clear();
			return;
		}
		int ok=0;
		for(int k=1;k<=m;k++)if(c2[k]==c[i]&&r[i]<r2[k]&&r2[k]<r[j]){
			ok=1;
		}
		if(ok)continue;
	//	cout<<c[i]<<" "<<r[i]+1<<" "<<r[j]-1<<'\n';
		liy[++cnty]=node(c[i],r[i]+1,r[j]-1);
	}
	tot=cntx+cnty;
	//cout<<cntx<<" "<<cnty<<'\n';
	str=++tot,des=++tot;
	for(int i=1;i<=cntx;i++)addedge(str,i,1);
	for(int i=1;i<=cnty;i++)addedge(i+cntx,des,1);
	for(int i=1;i<=cntx;i++)
	for(int j=1;j<=cnty;j++)if(inter(lix[i],liy[j])){
		addedge(i,j+cntx,1);
	}
	int res=Flow::dinic();
	cout<<cntx+cnty-res<<'\n';
	
	for(int i=1;i<=cntx;i++){
		int ok=0;
		for(auto x:e[i])if(x.v==str&&x.cap==1){
			ok=1;
		}
		if(ok==0){
			cout<<lix[i].t<<" "<<lix[i].l<<'\n';
		}
	}
	//cout<<"e1\n";
	for(int i=1;i<=cnty;i++){
		int ok=0;
		for(auto x:e[i+cntx])if(x.v==des&&x.cap==0){
			ok=1;
		}
		if(ok==0){
			cout<<liy[i+cntx].l<<" "<<liy[i+cntx].t<<'\n';
		}
	}
	//cout<<"e2\n";
	for(int i=1;i<=cntx;i++){
		for(auto x:e[i])if(x.v<=cntx+cnty&&x.cap==0){
			cout<<lix[i].t<<" "<<liy[i].t<<'\n';
		}
	}
	clear();
}

int main(){
    #ifdef Stargazer
    freopen("1.in","r",stdin);
    #endif
	int T=read();
	while(T--){
		solve();
	}
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11280kb

input:

4
7
1 3
6 6
4 7
2 1
6 3
4 1
2 6
3
3 4
6 4
3 1
2
1 1
2 2
0
3
1 1
1 3
3 3
1
1 2
3
1 1
1 3
2 3
0

output:

2
2 3
4 6
0
1
2 3
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 11292kb

input:

21
11
3 5
18 6
19 12
27 48
28 38
30 12
33 18
42 18
43 38
45 46
48 34
3
2 6
24 4
41 45
15
11 6
15 27
16 9
16 14
16 48
19 26
25 12
27 26
28 4
31 40
32 6
33 50
37 50
46 11
50 29
17
1 49
4 9
9 15
9 22
11 31
11 46
14 28
17 5
17 49
18 43
20 31
30 46
33 11
33 33
34 15
36 6
47 10
2
16 46
36 30
11
7 34
7 41
...

output:

3
20 12
29 38
34 18
6
16 10
16 10
16 15
0 0
0 0
0 0
0
1
16 10
0
1
43 22
6
1 3
1 3
1 13
33 10
44 45
0 0
0
5
27 41
29 26
44 4
0 0
0 0
1
32 9
0
0
0
0
7
12 11
23 10
23 44
29 21
0 0
23 46
35 0
0
3
20 30
43 25
30 34
0
-1
3
25 7
0 0
16 36
6
6 4
7 3
0 0
0 0
5 5
8 11

result:

wrong answer Integer parameter [name=x_i] equals to 0, violates the range [1, 10^9] (test case 2)