QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #691834 | #9424. Stop the Castle 2 | fzx | WA | 65ms | 52244kb | C++14 | 5.9kb | 2024-10-31 13:10:37 | 2024-10-31 13:10:37 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int INF=1e6+5;
int n,m,k,a[INF],b[INF],p[INF],p2[INF];
int c[INF],d[INF],vis5[INF],vis3[INF],vis4[INF];
vector <int> cnt2[INF];
namespace flow{
struct _node_edge{
int to_,next_,disv_,id;
}edge[INF<<1];
int tot,totn,head[INF],S,T,dep[INF];
queue <int> q;
void add_edge(int x,int y,int z,int zz) {
edge[++tot]={y,head[x],z,zz};
head[x]=tot;
swap(x,y);z=0;
edge[++tot]={y,head[x],z,0};
head[x]=tot;
}
int BFS(int s) {
for (int p=0;p<=totn;p++) dep[p]=0;
dep[s]=1;q.push(s);
while (q.size()) {
int x=q.front();q.pop();
for (int i=head[x];i;i=edge[i].next_) {
int v=edge[i].to_;
if (!edge[i].disv_) continue;
if (dep[v]) continue;
dep[v]=dep[x]+1;
q.push(v);
}
}
return dep[T]!=0;
}
int DFS(int x,int li) {
if (x==T) return li;
if (!li) return 0;
int sum=0;
for (int i=head[x];i;i=edge[i].next_) {
int v=edge[i].to_,d=edge[i].disv_;
if (!d) continue;
if (!li) break;
if (dep[v]!=dep[x]+1) continue;
int xx=DFS(v,min(li,d));
if (!xx) {dep[v]=1e9;continue;}
edge[i].disv_-=xx;edge[i^1].disv_+=xx;
sum+=xx;li-=xx;
}
return sum;
}
void main() {
while (BFS(S)) DFS(S,m-k);
for (int x=1;x<=totn;x++) {
for (int i=head[x];i;i=edge[i].next_) {
if (!edge[i].id) continue;
if (!edge[i].disv_) vis5[edge[i].id]=1,vis3[x]=1,vis4[edge[i].to_]=1;
}
}
}
};
int CNT;
void solve() {
// memset(flow::head,0,sizeof flow::head);
// memset(flow::dep,0,sizeof flow::dep);
// memset(flow::edge,0,sizeof flow::edge);
CNT++;
// cerr<<CNT<<" qwerij\n";
// // [200,210]
// if (CNT>=210) exit(0);
for (int w=0;w<=flow::totn;w++) flow::head[w]=vis3[w]=vis4[w]=0;
cin>>n>>m>>k; flow::tot=1;flow::totn=0;
for (int i=1;i<=n;i++) cin>>a[i]>>b[i];
for (int i=1;i<=m;i++) cin>>c[i]>>d[i],vis5[i]=0;
// if (CNT==586) {
// cerr<<n<<" "<<m<<" "<<k<<"\n";
// for (int i=1;i<=n;i++)
// cerr<<a[i]<<" "<<b[i]<<"\n";
// for (int i=1;i<=m;i++)
// cerr<<a[i]<<" "<<b[i]<<"\n";
// }
for (int i=1;i<=m;i++) cnt2[i].clear();
for (int i=1;i<=n;i++) p[i]=i;
for (int i=1;i<=m;i++) p2[i]=i;
sort(p+1,p+1+n,[](int x,int y){return a[x]!=a[y]?a[x]<a[y]:b[x]<b[y];});
sort(p2+1,p2+1+m,[](int x,int y){return c[x]!=c[y]?c[x]<c[y]:d[x]<d[y];});
int rr=0,res=0;
for (int l=1;l<=n;l++) {
int r=l;
while (r+1<=n && a[p[r+1]]==a[p[r]]) r++;
while (rr+1<=m && c[p2[rr+1]]<a[p[l]]) rr++;
for (int u=l;u<r;u++) {
flow::totn++;
int L=0;
while (rr+1<=m && c[p2[rr+1]]==a[p[u]] && d[p2[rr+1]]<b[p[u]]) rr++;
while (rr+1<=m && c[p2[rr+1]]==a[p[u]] && d[p2[rr+1]]<b[p[u+1]]) {
// cerr<<d[p2[rr+1]]<<" "<<b[p[u+1]]<<" qwoejr\n";
cnt2[p2[rr+1]].pb(flow::totn);
rr++;L=1;
}
// cerr<<b[p[u]]<<" "<<b[p[u+1]]<<" "<<d[p2[2]]<<" qwojit\n";
res++;
}
l=r;
}
int L=flow::totn;
for (int i=1;i<=n;i++) swap(a[i],b[i]);
for (int i=1;i<=m;i++) swap(c[i],d[i]);
sort(p+1,p+1+n,[](int x,int y){return a[x]!=a[y]?a[x]<a[y]:b[x]<b[y];});
sort(p2+1,p2+1+m,[](int x,int y){return c[x]!=c[y]?c[x]<c[y]:d[x]<d[y];});
rr=0;
for (int l=1;l<=n;l++) {
int r=l;
while (r+1<=n && a[p[r+1]]==a[p[r]]) r++;
while (rr+1<=m && c[p2[rr+1]]<a[p[l]]) rr++;
for (int u=l;u<r;u++) {
flow::totn++;
int L=0;
while (rr+1<=m && c[p2[rr+1]]==a[p[u]] && d[p2[rr+1]]<b[p[u]]) rr++;
while (rr+1<=m && c[p2[rr+1]]==a[p[u]] && d[p2[rr+1]]<b[p[u+1]]) {
cnt2[p2[rr+1]].pb(flow::totn);
rr++;L=1;
}
res++;
}
l=r;
}
flow::S=++flow::totn;
flow::T=++flow::totn;
for (int w=1;w<=L;w++) flow::add_edge(flow::S,w,1,0);
for (int w=L+1;w<=flow::totn-2;w++) flow::add_edge(w,flow::T,1,0);
for (int i=1;i<=m;i++) {
if (cnt2[i].size()<=1) continue;
flow::add_edge(cnt2[i][0],cnt2[i][1],1,i);
}
int Sum=m-k;
if (m-k) flow::main();
for (int i=1;i<=m;i++) Sum-=!!vis5[i],res-=(!!vis5[i])*2;
// cerr<<Sum<<" "<<res<<" qweroj\n";
for (int i=1;i<=m;i++) {
// cerr<<cnt2[i].size()<<" qwoiej\n";
if (vis5[i]) continue;
if (!Sum) break;
if (cnt2[i].size()==2) {
if ((vis3[cnt2[i][0]] || vis4[cnt2[i][0]]) &&
(vis3[cnt2[i][1]] || vis4[cnt2[i][1]])) continue;
vis3[cnt2[i][0]]=vis4[cnt2[i][0]]=1;
vis3[cnt2[i][1]]=vis4[cnt2[i][1]]=1;
Sum--;vis5[i]=1;res--;
}
}
for (int i=1;i<=m;i++) {
if (vis5[i]) continue;
if (!Sum) break;
if (cnt2[i].size()==1) {
if (vis3[cnt2[i][0]] || vis4[cnt2[i][0]]) continue;
vis3[cnt2[i][0]]=vis4[cnt2[i][0]]=1;
Sum--;vis5[i]=1;res--;
}
}
for (int i=1;i<=m;i++) {
if (vis5[i]) continue;
if (!Sum) break;
Sum--;vis5[i]=1;
}
cout<<res<<"\n";
for (int w=1;w<=m;w++)
if (!vis5[w]) cout<<w<<" ";
cout<<"\n";
}
signed main()
{
// freopen("data.in","r",stdin);
// freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
int t=0;cin>>t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 48588kb
input:
3 8 6 4 1 3 2 1 2 6 4 1 4 7 6 1 6 3 6 6 2 3 3 1 4 3 4 6 5 2 6 4 3 2 1 10 12 10 10 10 11 1 4 1 5 1 3 2 1 1 2 1 2 2 2 3
output:
4 2 3 5 6 2 2 0 2 3
result:
ok ok 3 cases (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 65ms
memory: 52244kb
input:
1224 11 17 14 7 3 4 2 8 13 3 15 3 4 5 11 10 2 3 3 8 6 7 11 2 3 10 4 1 3 12 1 2 5 11 9 11 6 11 10 8 15 1 5 9 14 4 11 1 6 10 7 7 6 11 4 8 4 1 11 18 3 2 14 8 2 14 13 13 9 12 14 12 5 6 8 1 10 5 8 6 8 9 6 6 7 5 12 11 6 11 13 5 1 10 7 6 14 5 6 15 2 4 11 1 1 6 4 14 14 13 9 9 3 10 12 7 5 8 13 9 14 1 9 8 4 9...
output:
7 3 4 5 6 7 8 9 10 11 12 13 15 16 17 15 2 3 0 3 4 5 6 0 2 3 4 5 6 7 8 9 11 1 3 8 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 12 1 5 6 7 9 10 11 12 8 17 18 19 1 1 2 3 4 5 6 7 8 7 6 8 10 13 14 15 1 10 11 12 13 14 15 16 17 18 19 20 0 1 1 2 3 0 5 6 7 7 8 12 13 14 15 2 10 11 12 13 14 4 3 4 5 6 7 8 ...
result:
wrong answer Integer parameter [name=b_i] equals to 12, violates the range [1, 11] (test case 207)