QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#605810#9412. Stop the CastlezqxWA 0ms28340kbC++235.0kb2024-10-02 19:43:572024-10-02 19:43:57

Judging History

This is the latest submission verdict.

  • [2024-10-02 19:43:57]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 28340kb
  • [2024-10-02 19:43:57]
  • 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;
    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});
                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<<'\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: 0
Wrong Answer
time: 0ms
memory: 28340kb

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 3
4 6
2 3
-1

result:

wrong answer Duplicated position (3, 4) (test case 1)