QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#609684 | #9412. Stop the Castle | ucup-team902# | WA | 2ms | 11256kb | C++17 | 3.9kb | 2024-10-04 13:43:10 | 2024-10-04 13:43:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define ll long long
#define pii pair<ll,ll>
#define gc getchar
#define fi first
#define se second
#define bg begin
template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}
inline int read(){
char ch=gc();
int res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
cs int N=100005;
int n,m;
int str,des,tot;
struct edge{
int v,cap,r;
edge(int a=0,int b=0,int c=0):v(a),cap(b),r(c){}
};
vector<edge> e[N];
inline void addedge(int u,int v,int w){
e[u].pb(edge(v,w,e[v].size()));
e[v].pb(edge(u,0,e[u].size()-1));
}
#define It vector<edge>::iterator
namespace Flow{
int lev[N];It tp[N];
queue<int> q;
inline bool bfs(){
memset(lev,-1,sizeof(int)*(tot+1));
lev[str]=0,q.push(str);
while(!q.empty()){
int u=q.front();q.pop();
for(edge &x:e[u]){
if(lev[x.v]==-1&&x.cap>0){
lev[x.v]=lev[u]+1,q.push(x.v);
}
}
}
return lev[des]!=-1;
}
int dfs(int u,int flow){
if(u==des)return flow;
int res=0;
for(It &it=tp[u];it!=e[u].end();it++){
if(lev[it->v]==lev[u]+1&&it->cap>0){
int now=dfs(it->v,min(it->cap,flow-res));
res+=now,it->cap-=now,e[it->v][it->r].cap+=now;
if(res==flow)break;
}
}
return res;
}
inline int dinic(){
int res=0;
while(bfs()){
for(int i=1;i<=tot;i++)tp[i]=e[i].bg();
res+=dfs(str,1e9);
}
return res;
}
}
int r[N],c[N],cntx,cnty;
int r2[N],c2[N];
void clear(){
for(int i=0;i<=tot;i++)e[i].clear();
str=des=tot=0;
}
struct node{
int t,l,r;
node(int _t=0,int _l=0,int _r=0):t(_t),l(_l),r(_r){}
}lix[N],liy[N];
int inter(node x,node y){
return y.l<=x.t&&x.t<=y.r&&x.l<=y.t&&y.t<=x.r;
}
void solve(){
n=read();cntx=cnty=0;
for(int i=1;i<=n;i++)r[i]=read(),c[i]=read();
m=read();
for(int i=1;i<=m;i++)r2[i]=read(),c2[i]=read();
tot=0,str=++tot,des=++tot;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(i!=j&&r[i]==r[j]&&c[i]<c[j]){
if(c[i]+1==c[j]){
puts("-1");
clear();
return;
}
int ok=0;
for(int k=1;k<=m;k++)if(r[k]==r[i]&&c[i]<c[k]&&c[k]<c[j]){
ok=1;
}
for(int k=1;k<=m;k++)if(r2[k]==r[i]&&c[i]<c2[k]&&c2[k]<c[j]){
ok=1;
}
if(ok)continue;
//cout<<i<<" "<<j<<'\n';
// cout<<r[i]<<" "<<c[i]+1<<" "<<c[j]-1<<'\n';
lix[++cntx]=node(r[i],c[i]+1,c[j]-1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)if(i!=j&&c[i]==c[j]&&r[i]<r[j]){
if(r[i]+1==r[j]){
puts("-1");
clear();
return;
}
int ok=0;
for(int k=1;k<=m;k++)if(c[k]==c[i]&&r[i]<r[k]&&r[k]<r[j]){
ok=1;
}
for(int k=1;k<=m;k++)if(c2[k]==c[i]&&r[i]<r2[k]&&r2[k]<r[j]){
ok=1;
}
if(ok)continue;
// cout<<c[i]<<" "<<r[i]+1<<" "<<r[j]-1<<'\n';
liy[++cnty]=node(c[i],r[i]+1,r[j]-1);
}
tot=cntx+cnty;
//cout<<cntx<<" "<<cnty<<'\n';
str=++tot,des=++tot;
for(int i=1;i<=cntx;i++)addedge(str,i,1);
for(int i=1;i<=cnty;i++)addedge(i+cntx,des,1);
for(int i=1;i<=cntx;i++)
for(int j=1;j<=cnty;j++)if(inter(lix[i],liy[j])){
addedge(i,j+cntx,1);
}
int res=Flow::dinic();
cout<<cntx+cnty-res<<'\n';
for(int i=1;i<=cntx;i++){
int ok=0;
for(auto x:e[i])if(x.v==str&&x.cap==1){
ok=1;
}
if(ok==0){
cout<<lix[i].t<<" "<<lix[i].l<<'\n';
}
}
//cout<<"e1\n";
for(int i=1;i<=cnty;i++){
int ok=0;
for(auto x:e[i+cntx])if(x.v==des&&x.cap==0){
ok=1;
}
if(ok==0){
cout<<liy[i].l<<" "<<liy[i].t<<'\n';
}
}
//cout<<"e2\n";
for(int i=1;i<=cntx;i++){
for(auto x:e[i])if(x.v<=cntx+cnty&&x.cap==0){
cout<<lix[i].t<<" "<<liy[i].t<<'\n';
}
}
clear();
}
int main(){
#ifdef Stargazer
freopen("1.in","r",stdin);
#endif
int T=read();
while(T--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 11016kb
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: -100
Wrong Answer
time: 0ms
memory: 11256kb
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 29 38 34 18 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 12 11 23 44 29 21 24 46 23 46 35 0 0 3 20 30 43 25 31 17 0 -1 3 25 7 17 39 16 36 6 6 4 7 3 3 10 2 11 5 5 8 11
result:
wrong answer Integer parameter [name=y_i] equals to 0, violates the range [1, 10^9] (test case 15)