QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#769390 | #9412. Stop the Castle | qvzeyang | WA | 1ms | 5848kb | C++23 | 4.8kb | 2024-11-21 17:27:31 | 2024-11-21 17:27:36 |
Judging History
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)