QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#605810 | #9412. Stop the Castle | zqx | WA | 0ms | 28340kb | C++23 | 5.0kb | 2024-10-02 19:43:57 | 2024-10-02 19:43:57 |
Judging History
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)