QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#111670 | #6308. Magic | XZC0920 | WA | 9ms | 13000kb | C++14 | 1.8kb | 2023-06-07 20:41:11 | 2023-06-07 20:41:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,INF=1e9;
int n,l,r,rt,cnt,s,t,tot=1,h[N],now[N],ans,d[N];
tuple<int,int> a[N];
struct edge {int to,val,nxt;}e[N<<2];
void Add(int u,int v,int w)
{
e[++tot]={v,w,h[u]};
h[u]=tot;
}
void add(int u,int v,int w)
{
Add(u,v,w);
Add(v,u,0);
}
bool bfs()
{
queue<int> q;
for(int i=1;i<=cnt;i++) d[i]=0,now[i]=h[i];
q.push(s);d[s]=1;
while(q.size())
{
int u=q.front();q.pop();
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].val;
if(w==0||d[v]) continue;
d[v]=d[u]+1;q.push(v);
if(v==t) return 1;
}
}
return 0;
}
int dinic(int u,int sum)
{
if(u==t) return sum;
int res=sum;
for(int &i=now[u];i;i=e[i].nxt)
{
int v=e[i].to,w=e[i].val;
if(w==0||d[v]!=d[u]+1) continue;
int k=dinic(v,min(res,w));
if(!k) d[v]=0;
e[i].val-=k;e[i^1].val+=k;res-=k;
if(res==0) break;
}
return sum-res;
}
struct SegTree
{
#define mid ((l+r)>>1)
int ls[N],rs[N];
void modify(int &p,int q,int l,int r,int x)
{
p=++cnt;ls[p]=ls[q];rs[p]=rs[q];
if(l==r) return add(p,x,1);
(x<=mid)?modify(ls[p],ls[q],l,mid,x):modify(rs[p],rs[q],mid+1,r,x);
if(ls[p]) add(p,ls[p],1);
if(rs[p]) add(p,rs[p],1);
}
void update(int p,int l,int r,int L,int R)
{
if(p==0) return;
if(L<=l&&r<=R) return add(L,p,1);
if(L<=mid) update(ls[p],l,mid,L,R);
if(R>mid) update(rs[p],mid+1,r,L,R);
}
}T;
int main()
{
scanf("%d",&n);cnt=n+n;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&l,&r);
a[i]=make_tuple(l,r);
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
tie(l,r)=a[i];
T.update(rt,1,n+n,l,r);
T.modify(rt,rt,1,n+n,r);
}
s=++cnt,t=++cnt;
for(int i=1;i<=n;i++)
{
tie(l,r)=a[i];
add(s,l,1);add(r,t,1);
}
while(bfs()) ans+=dinic(s,INF);
ans=n+n-ans;
printf("%d\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7732kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 3ms
memory: 12996kb
input:
5000 7985 7987 42 46 1591 1593 407 410 6305 6306 1456 1457 5874 5875 7135 7137 7041 7046 6813 6815 8868 8871 665 666 4055 4056 9789 9796 7067 7068 4745 4746 5167 5171 1735 1737 2125 2128 1444 1447 1348 1352 6087 6090 1381 1384 1600 1601 5187 5190 2801 2802 8449 8450 9376 9377 4021 4024 2674 2676 490...
output:
8134
result:
ok 1 number(s): "8134"
Test #3:
score: -100
Wrong Answer
time: 9ms
memory: 13000kb
input:
5000 3171 3172 4062 4064 4647 4651 3670 3673 7112 7114 9714 9717 3781 3789 8422 8426 457 460 5450 5454 7113 7122 6313 6320 9969 9973 828 832 6878 6892 4476 4483 892 903 251 259 6304 6315 130 134 9206 9215 2679 2686 9090 9091 8222 8228 9374 9375 2985 2989 3397 3401 4916 4918 6819 6821 883 889 2516 25...
output:
7073
result:
wrong answer 1st numbers differ - expected: '7047', found: '7073'