QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#605815#9412. Stop the CastlezqxWA 85ms125884kbC++235.0kb2024-10-02 19:48:012024-10-02 19:48:02

Judging History

This is the latest submission verdict.

  • [2024-10-02 19:48:02]
  • Judged
  • Verdict: WA
  • Time: 85ms
  • Memory: 125884kb
  • [2024-10-02 19:48:01]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
struct Dinic {
	long long INF = 1e18;
	int SIZ = 5e5 + 3;
	int n, m;
	int H[5000005], V[5000005], N[5000005], F[5000005], t = 1;
	int add(int u, int v, int f) {
		V[++ t] = v, N[t] = H[u], F[t] = f, H[u] = t;
		V[++ t] = u, N[t] = H[v], F[t] = 0, H[v] = t;
		n = max(n, u);
		n = max(n, v);
		return t;
	}
	void clear() {
		for (int i = 1; i <= n; ++ i)
			H[i] = 0;
		n = m = 0, t = 1;
	}
	int D[5000005];
	bool bfs(int s, int t) {
		queue <int> Q;
		for (int i = 1; i <= n; ++ i)
			D[i] = 0;
		Q.push(s), D[s] = 1;
		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			for (int i = H[u]; i; i = N[i]) {
				const int &v = V[i];
				const int &f = F[i];
				if (f != 0 && !D[v]) {
					D[v] = D[u] + 1;
					Q.push(v);
				}
			}
		}
		return D[t] != 0;
	}
	int C[5000005];
	long long dfs(int s, int t, int u, long long maxf) {
		if (u == t)
			return maxf;
		long long totf = 0;
		for (int &i = C[u]; i; i = N[i]) {
			const int &v = V[i];
			const int &f = F[i];
			if (D[v] == D[u] + 1) {
				long long resf = dfs(s, t, v, min(maxf, 1ll * f));
				totf += resf;
				maxf -= resf;
				F[i    ] -= resf;
				F[i ^ 1] += resf;
				if (maxf == 0)
					return totf;
			}
		}
		return totf;
	}
	long long dinic(int s, int t) {
		long long ans = 0;
		while (bfs(s, t)) {
			memcpy(C, H, sizeof(H));
			ans += dfs(s, t, s, INF);
		}
		return ans;
	}
} a;
#define all(tar) tar.begin(),tar.end()
int n,m;
const int maxx=2e3+5;
int mp[maxx][maxx];//0无 1防御塔 2障碍
vector<int>num;
int get_pos(int x){
    return lower_bound(all(num),x)-num.begin()+1;
}
pair<int,int>p1[maxx],p2[maxx];
int id[maxx][maxx][2],idx;
int G1[maxx][maxx],G2[maxx][maxx];
void solve(){
    a.clear();
    num.clear();
    idx=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p1[i].first>>p1[i].second;
        num.push_back(p1[i].first);
        num.push_back(p1[i].second);
        num.push_back(p1[i].first+1);
        num.push_back(p1[i].second+1);
    }
    cin>>m;
    int s=++idx,t=++idx;
     for(int i=1;i<=m;i++){
        cin>>p2[i].first>>p2[i].second;
        num.push_back(p2[i].first);
        num.push_back(p2[i].second);
        num.push_back(p2[i].first+1);
        num.push_back(p2[i].second+1);
    }  
    sort(all(num)); 
    int len=num.size();
    num.erase(unique(all(num)),num.end());
      for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
           G1[i][j]=G2[i][j]=mp[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
       int x=get_pos(p1[i].first);
       int y=get_pos(p1[i].second);
       mp[x][y]=2; 
    }
    for(int i=1;i<=m;i++){
       int x=get_pos(p2[i].first);
       int y=get_pos(p2[i].second);
       mp[x][y]=1; 
    }
    int ans=0;
    for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
            id[i][j][0]=++idx;
            id[i][j][1]=++idx;
            a.add(s,id[i][j][0],1);
            a.add(id[i][j][1],t,1);
            if(mp[i][j]==2){
                if(mp[i-1][j]==2||mp[i][j-1]==2){
                    cout<<"-1\n";
                    return ;
                }
            }
        }
    }
    for(int i=1;i<=len;i++){
      int pre=0;
      for(int j=1;j<=len;j++){
        if(mp[i][j]==2){
           if(pre){
               ++ans;
              for(int k=pre+1;k<j;k++){
               G1[i][k]=pre;
              }
          }
          pre=j;
        }else if(mp[i][j]==1){
           pre=0;
        }
      }
    }
    for(int i=1;i<=len;i++){
      int pre=0;
      for(int j=1;j<=len;j++){
        if(mp[j][i]==2){
          if(pre){
            ++ans;
             for(int k=pre+1;k<j;k++){
             G2[k][i]=pre;
             }
          }
          pre=j;
        }else if(mp[j][i]==1){
           pre=0;
        }
      }
    }
    vector<array<int,3>>e;
    int c=0;
    for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
            if(G1[i][j]&&G2[i][j]){
                e.push_back({i,j,a.t+1});
                ++c;
                a.add(id[i][G1[i][j]][0],id[G2[i][j]][j][1],1);
            }
        }
    }
    int p=a.dinic(s,t);
    if(n==200)cout<<ans<<" "<<p<<" "<<c<<'\n';
    cout<<ans-p<<'\n';
   for(auto [x,y,z]:e){
     if(a.F[z]==0)cout<<num[x-1]<<" "<<num[y-1]<<'\n',mp[x][y]=1;
   }
    for(int i=1;i<=len;i++){
      int pre=0;
      for(int j=1;j<=len;j++){
        if(mp[i][j]==2){
           if(pre){
              cout<<num[i-1]<<" "<<num[pre]<<'\n';
          }
          pre=j;
        }else if(mp[i][j]==1){
           pre=0;
        }
      }
    }
    for(int i=1;i<=len;i++){
      int pre=0;
      for(int j=1;j<=len;j++){
        if(mp[j][i]==2){
          if(pre){
             cout<<num[pre]<<" "<<num[i-1]<<'\n';
          }
          pre=j;
        }else if(mp[j][i]==1){
           pre=0;
        }
      }
    }
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
      solve();
    }
}

詳細信息

Test #1:

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

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: 0
Accepted
time: 7ms
memory: 48336kb

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
34 18
29 38
5
16 10
16 15
12 6
20 26
34 50
0
1
16 10
0
1
43 22
5
1 3
1 13
33 10
44 45
42 44
0
5
27 41
29 26
44 4
8 1
21 15
1
32 9
0
0
0
0
6
23 10
35 34
12 11
23 44
29 21
24 46
0
3
20 30
43 25
31 17
0
-1
3
16 36
25 7
17 39
6
7 5
8 11
5 5
6 4
4 9
3 10

result:

ok ok 21 cases (21 test cases)

Test #3:

score: -100
Wrong Answer
time: 85ms
memory: 125884kb

input:

2
200
7 52
9 160
10 4
12 61
18 436
19 430
20 499
24 139
25 416
29 53
33 153
35 275
35 310
37 25
38 477
39 349
42 120
44 158
45 330
49 486
50 204
51 67
52 138
52 305
56 139
63 132
66 4
67 327
70 484
71 67
72 308
74 218
76 479
81 139
82 90
86 201
87 335
91 35
91 220
92 496
94 29
94 436
96 359
97 299
1...

output:

66 20 106
46
52 139
91 160
94 35
126 61
132 67
154 138
154 496
185 147
187 467
199 432
224 153
260 275
270 305
277 356
306 374
311 186
334 367
349 61
352 112
393 307
35 276
126 214
187 433
224 393
261 468
274 67
277 189
311 455
390 308
440 179
453 251
11 4
38 25
240 35
52 67
57 139
292 177
271 186
2...

result:

wrong answer There are still 63 pairs of castles which can attack each other (test case 1)