QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769390#9412. Stop the CastleqvzeyangWA 1ms5848kbC++234.8kb2024-11-21 17:27:312024-11-21 17:27:36

Judging History

This is the latest submission verdict.

  • [2024-11-21 17:27:36]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 5848kb
  • [2024-11-21 17:27:31]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pr pair<int,int>
#define _(x,y) x=(x+y)%mod
#define ll long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
#define N 405
int n,m,X[N],Y[N],lsh[N],cnt,S,T;
#define fi first
#define se second
vector<pair<int,int> > row[N];
vector<pair<int,pair<int,int> > > L,R;
struct edge{
    int b,c,n;
}e[N*N*10];
int h[N*10],tot=1;
inline void charu(int a,int b,int c){
    e[++tot].b=b,e[tot].c=c,e[tot].n=h[a],h[a]=tot;
    e[++tot].b=a,e[tot].c=0,e[tot].n=h[b],h[b]=tot;
}
queue<int> q;
int dep[N*5],cur[N*5];
inline bool bfs(){
    memset(dep,-1,sizeof(dep));
    memcpy(cur,h,sizeof(cur));
    dep[S]=0,q.push(S);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u];i;i=e[i].n){
            int v=e[i].b;
            if(e[i].c && dep[v]==-1){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[T]!=-1;
}
int dfs(int u,int limit){
    if(u==T || limit==0) return limit;
    int flow=0,tmp;
    for(int &i=cur[u];i;i=e[i].n){
        int v=e[i].b;
        if(dep[u]+1==dep[v] && e[i].c && (tmp=dfs(v,min(limit,e[i].c)))){
            e[i].c-=tmp,e[i^1].c+=tmp;
            flow+=tmp,limit-=tmp;
            if(!limit) break;
        }
    }
    return flow;
}
inline int dinic(){
    int maxflow=0;
    while(bfs()){
        maxflow+=dfs(S,1e9);
    }
    return maxflow;
}
signed main(){
    for(int cas=read();cas--;){
        L.clear(),R.clear();
        n=read();
        for(int i=1;i<=n;++i){
            X[i]=read(),Y[i]=read();
        }
        m=read();
        for(int i=1;i<=m;++i){
            X[i+n]=read(),Y[i+n]=read();
        }
        cnt=0;
        for(int i=1;i<=n+m;++i) lsh[++cnt]=X[i];
        sort(lsh+1,lsh+cnt+1);
        cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
        for(int i=1;i<=n+m;++i){
            int tmp=lower_bound(lsh+1,lsh+cnt+1,X[i])-lsh;
            row[tmp].push_back({Y[i],i});
        }
        int flag=1,ans=0;
        for(int i=1;i<=cnt;++i){
            sort(row[i].begin(),row[i].end());
            for(int j=0;j+1<row[i].size();++j){
                if(row[i][j].se<=n && row[i][j+1].se<=n){
                    if(row[i][j].fi+1==row[i][j+1].fi){
                        flag=0;
                    }
                    L.push_back({lsh[i],{row[i][j].fi,row[i][j+1].fi}});
                    ans++;
                }
            }
            row[i].clear();
        }
        cnt=0;
        for(int i=1;i<=n+m;++i) lsh[++cnt]=Y[i];
        sort(lsh+1,lsh+cnt+1);
        cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
        for(int i=1;i<=n+m;++i){
            int tmp=lower_bound(lsh+1,lsh+cnt+1,Y[i])-lsh;
            row[tmp].push_back({X[i],i});
        }
        for(int i=1;i<=cnt;++i){
            sort(row[i].begin(),row[i].end());
            for(int j=0;j+1<row[i].size();++j){
                if(row[i][j].se<=n && row[i][j+1].se<=n){
                    if(row[i][j].fi+1==row[i][j+1].fi){
                        flag=0;
                    }
                    R.push_back({lsh[i],{row[i][j].fi,row[i][j+1].fi}});
                    ans++;
                }
            }
            row[i].clear();
        }
        int pool=0;
        if(flag){
            pool=L.size()+R.size()+1;
            S=pool-1,T=pool;
            for(int i=0;i<L.size();++i) charu(S,i,1);
            for(int i=0;i<R.size();++i) charu(i+L.size(),T,1);
            for(int i=0;i<L.size();++i){
                auto u=L[i];
                for(int j=0;j<R.size();++j){
                    auto v=R[j];
                    if(u.se.fi<v.fi && v.fi<u.se.se && v.se.fi<u.fi && u.fi<u.se.se){
                        charu(i,j+L.size(),1);
                    }
                }
            }
            printf("%d\n",ans-dinic());
            for(int i=2;i<=tot;i+=2){
                if(e[i].b==T || e[i^1].b==S) continue;
                if(!e[i].c){
                    int u=e[i^1].b,v=e[i].b-L.size();
                    printf("%d %d\n",L[u].fi,R[v].fi);
                }
            }
            for(int i=2;i<=tot;i+=2){
                if(e[i].c && e[i^1].b==S){
                    int u=e[i].b;
                    printf("%d %d\n",L[u].fi,L[u].se.fi+1);
                }
            }
            for(int i=2;i<=tot;i+=2){
                if(e[i].c && e[i].b==T){
                    int v=e[i^1].b-L.size();
                    printf("%d %d\n",R[v].se.fi+1,R[v].fi);
                }
            }
        }
        else{
            puts("-1");
        }
        tot=1;
        for(int i=0;i<=pool;++i) h[i]=0;
    }
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3808kb

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: 1ms
memory: 5848kb

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: 1ms
memory: 3752kb

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:

46
52 160
91 138
94 139
126 139
132 67
154 305
154 496
185 147
187 436
187 467
199 153
224 67
224 429
260 275
270 374
277 356
306 432
311 367
311 477
334 367
35 276
126 214
261 468
274 67
277 189
349 59
352 36
390 308
393 29
440 179
453 251
11 4
38 25
92 35
240 35
13 61
312 61
275 112
292 177
271 18...

result:

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