QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609969#9412. Stop the CastleKanate#WA 21ms35296kbC++144.9kb2024-10-04 14:36:182024-10-04 14:36:20

Judging History

This is the latest submission verdict.

  • [2024-10-04 14:36:20]
  • Judged
  • Verdict: WA
  • Time: 21ms
  • Memory: 35296kb
  • [2024-10-04 14:36:18]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define int long long
const int INF = 1e9 + 7;
const int M = 1e6 + 7;
const int N = 1e6 + 7;
int n , m , s , t , cnt =1 ;
int T;
int lv[N],cur[N];
struct edge{
	int v , nex , flow;
}e[M];int head[N];
int X[N],Y[N];
int fx[N],fy[N];
bool bfs(){
	memset(lv,-1,sizeof lv);
	lv[s] = 0 ;
	memcpy(cur,head,sizeof cur);
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i = head[x];i;i = e[i].nex){
			int v = e[i].v;
			int val = e[i].flow;
			if(val > 0 && lv[v] == -1){
				lv[v] = lv[x] + 1;
				q.push(v);
			}
		}
	}
	return lv[t] != -1;
}

int dfs(int x=s,int flow = INF){
	if(x==t) return flow;
	int rmn = flow;
	for(int i=cur[x];i && rmn;i=e[i].nex){
		cur[x] = i;
		int v = e[i].v;
		int val = e[i].flow;
		if(val > 0 && lv[v] == lv[x] + 1){
			int c = dfs(v,min(val,rmn));
			rmn -= c;
			e[i].flow -= c;
			e[i^1].flow += c;
		}
	}
	return flow - rmn;
}
void add(int u,int v,int flow){
	e[++cnt].v = v;
	e[cnt].nex = head[u];
	head[u] = cnt;
	e[cnt].flow = flow;
}
void add_edge(int u,int v,int flow){
	//cout <<"ADD " << u << " " << v << " " << flow << endl;
	add(u,v,flow);
	add(v,u,0);
}
vector<int>h,r;
unordered_map<int,int> recal_R;
unordered_map<int,int> recal_H;
int pd[2001][2001];
int id[2001][2001];
struct wqweqweq{
	int x , y;
}qwq[M];
int mx,my;
int tot = 0 ;
int GET_id(int x,int y){
	return (x-1) * (my+1) + y;
}

void print(){
			for(int i=1;i<=mx;i++){
			int las = - 1;
			for(int j=1;j<=my;j++){
				if(pd[i][j] == 1) {
 					if(las == -1) las = j;
					else {
						pd[i][j-1] = 3; 
						las = j;
					}
				}
				if(pd[i][j] == 2 || pd[i][j] == 3){
					las = -1;
				} 
			}
		}
		for(int j = 1;j<=my;j++){
			int las = - 1;
			for(int i=1;i<=mx;i++){
				if(pd[i][j] == 1){
					if(las==-1) las = i;
					else {
						pd[i-1][j] = 3; 
						las = i;
					}
				}
				if(pd[i][j] == 2 || pd[i][j] == 3){
					las = -1;
				} 
			}
		}
	for(int i=1;i<=mx;i++)
	for(int j=1;j<=my;j++)
	if(pd[i][j] == 3){
		cout << h[i-1] << " " << r[j-1] << endl;
	}
}
map<pair<int,int>,pair<int,int>>nowmp;
void solve(){
	nowmp.clear();
		int ans = 0 ;
		for(int i=1;i<=mx;i++){
			int las = - 1;
			for(int j=1;j<=my;j++){
				if(pd[i][j] == 1) {
 					if(las == -1) las = j;
					else {
						if(r[las-1]+1 == r[j-1]){
							cout << -1 << endl;
							return ;
						}
						++ tot;
						qwq[tot] = {i,j};
						ans ++ ;
						for(int k= las+1;k<=j-1;k++) id[i][k] = tot;
						add_edge(0,tot,1);
						las = j;
					}
				}
				if(pd[i][j] == 2){
					las = -1;
				} 
			}
		}
		t = ++ tot;
		for(int j = 1;j<=my;j++){
			int las = - 1;
			for(int i=1;i<=mx;i++){
				if(pd[i][j] == 1){
					if(las==-1) las = i;
					else {
						if(h[las-1]+1 == h[i-1]) {
							cout << -1 << endl;
							return ;
						}
						++ tot;
						ans ++ ;
						for(int k=las+1;k<=i-1;k++) 
						if(id[k][j]){
							add_edge(id[k][j],tot,1);
							nowmp[make_pair(id[k][j],tot)] = make_pair(k,j);
						}
						add_edge(tot,t,1);
						las = i;
					}
				}
				if(pd[i][j] == 2){
					las = - 1;
				}
			}
		}
	while(bfs()){
	//	cout << ans << endl;
		ans -= dfs();
	}
	for(int i = head[0];i;i=e[i].nex) {
		int v = e[i].v;
		for(int j=head[v];j;j=e[j].nex){
			int w = e[j].v;
			if(w==0 || e[j].flow==1) continue;
			pair<int,int> nod = nowmp[make_pair(v,w)];
			pd[nod.first][nod.second] = 3;
		}
	}

	cout << ans << endl;
	print();

	for(int i=0;i<=tot;i++) head[i]  = 0 ;
	for(int i=1;i<=mx;i++)
	for(int j=1;j<=my;j++)
	pd[i][j] = id[i][j] = 0 ;
	tot =  0;
	//cout << ans << endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T-->0){
		cin >> n ;
		h.clear();recal_R.clear();
		r.clear();recal_H.clear();cnt = 1;
		mx = my = 0 ;
		for(int i=1;i<=n;i++){
			int x , y;
			cin >> x >> y;
			X[i] = x;
			Y[i] = y; 
			h.emplace_back(x);
			r.emplace_back(y);
		}
		cin >> m;
		for(int i=1;i<=m;i++){
			cin >> fx[i] >> fy[i];
			h.emplace_back(fx[i]);
			r.emplace_back(fy[i]);
		}
		sort(h.begin(),h.end());
		sort(r.begin(),r.end());
		r.resize(unique(r.begin(),r.end())-r.begin());
		h.resize(unique(h.begin(),h.end())-h.begin());
		int rs = (int)r.size() - 1;
		int hs = (int)h.size() - 1;
		for(int i=0;i<rs;i++) 
		if(r[i]+1 != r[i+1]) r.emplace_back(r[i]+1);
		for(int i=0;i<hs;i++) 
		if(h[i]+1 != h[i+1]) h.emplace_back(h[i]+1);
		sort(h.begin(),h.end());
		sort(r.begin(),r.end());
		for(int i=0;i<r.size();i++)
			recal_R[r[i]]  = i+1;
		my = (int)r.size()  ;
		for(int i=0;i<h.size();i++)
			recal_H[h[i]]  = i+1;

		
		mx = (int)h.size() ;

		for(int i=1;i<=n;i++)
			pd [recal_H[X[i]]][recal_R[Y[i]]] = 1;
		for(int i=1;i<=m;i++)
			pd [recal_H[fx[i]]][recal_R[fy[i]]] = 2;
		solve();
		 
	}
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 34016kb

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: 21ms
memory: 35296kb

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
29 12
41 18
42 38
5
16 13
16 47
26 26
31 6
36 50
0
1
42 10
0
1
43 31
5
1 10
1 38
33 47
43 44
44 46
0
5
10 1
27 41
29 40
30 15
44 35
1
32 12
0
0
0
0
6
12 40
23 10
23 45
29 33
34 46
35 34
0
3
20 31
34 17
43 32
0
-1
-1
-1

result:

wrong answer Participant does not find an answer but the jury finds 3 (test case 20)