QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#605813#9412. Stop the CastlezqxWA 36ms90672kbC++235.0kb2024-10-02 19:46:322024-10-02 19:46:33

Judging History

This is the latest submission verdict.

  • [2024-10-02 19:46:33]
  • Judged
  • Verdict: WA
  • Time: 36ms
  • Memory: 90672kb
  • [2024-10-02 19:46:32]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
struct Dinic {
	long long INF = 1e18;
	int SIZ = 5e5 + 3;
	int n, m;
	int H[2000005], V[2000005], N[2000005], F[2000005], 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[2000005];
	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[2000005];
	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();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 33056kb

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: 36ms
memory: 90672kb

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 2064514 106
-2064448
52 139
52 153
52 160
52 275
91 61
91 67
91 138
91 153
91 160
94 35
94 61
94 67
94 138
94 153
94 160
94 275
94 305
126 61
126 67
126 138
126 153
126 160
126 275
132 35
132 61
132 67
132 138
132 153
132 160
132 275
132 305
154 138
154 153
154 160
154 275
154 305
154 374
154 467...

result:

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