QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#742418#9424. Stop the Castle 2Nana7RE 2ms26160kbC++144.2kb2024-11-13 16:35:022024-11-13 16:35:03

Judging History

This is the latest submission verdict.

  • [2024-11-13 16:35:03]
  • Judged
  • Verdict: RE
  • Time: 2ms
  • Memory: 26160kb
Show
  • [2024-11-13 16:35:02]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<queue> 
#define I inline
#define inf (int)(1e9)
#define it set<int>::iterator 
using namespace std;

const int N = 100010;
struct node {
	int x,y;
}c[N],o[N];
int n,m,K,L[N],U[N],D[N],R[N],ans[N],del[N<<1];
set<int> stx[N],sty[N];

const int MAXM = 1200010;
const int MAXN = 200010;
int S=200009,T=200008;
int head[MAXN],cur[MAXN],dis[MAXN],vis[MAXN];
int ver[MAXM],mf[MAXM],Next[MAXM],id[MAXM];
int tot=1;
queue<int> jr;

I void add(int x,int y,int nf,int nid) {
	ver[++tot]=y; mf[tot]=nf; Next[tot]=head[x]; head[x]=tot; id[tot]=nid;
	ver[++tot]=x; mf[tot]=0; Next[tot]=head[y]; head[y]=tot; id[tot]=nid;
}
I bool spfa() {
	while(!jr.empty()) jr.pop();
	for(int i=1;i<=n*2;++i) dis[i]=inf,vis[i]=0;
	vis[S]=1; dis[S]=0; vis[T]=0; dis[T]=inf; jr.push(S);
	while(!jr.empty()) {
		int k=jr.front(); jr.pop(); vis[k]=0;
		for(int i=head[k];i;i=Next[i]) {
			int to=ver[i];
			if(!mf[i]) continue;
			if(dis[k]+1<dis[to])	{
			  	dis[to]=dis[k]+1;
			  	if(!vis[to]) vis[to]=1,jr.push(to);
			}
		}
	}
	if(dis[T]==inf) return false;
	return true;
}
I int dfs(int x,int limit) { 
	if(!limit) return 0;
	if(x==T) return limit;
	vis[x]=1;
	int nowflow=0;
	for(int i=cur[x];i;i=Next[i]) {
		if(!(limit-nowflow)) continue;
		int to=ver[i];
		cur[x]=i;
		if(vis[to]||(!mf[i])||dis[to]!=dis[x]+1) continue;
		int f=dfs(to,min(limit-nowflow,mf[i]));
		if(!f) continue;
		mf[i]-=f; mf[i^1]+=f;
		nowflow+=f; 
	}
	vis[x]=0;
	return nowflow;
}
I void ck1() {
	cout<<"L: ";
	for(int i=1;i<=n;++i) cout<<L[i]<<' '; cout<<endl;
	cout<<"R: ";
	for(int i=1;i<=n;++i) cout<<R[i]<<' '; cout<<endl; 
	cout<<"U: ";
	for(int i=1;i<=n;++i) cout<<U[i]<<' '; cout<<endl;
	cout<<"D: ";
	for(int i=1;i<=n;++i) cout<<D[i]<<' '; cout<<endl;
}
#define mkp make_pair
#define pii pair<int,int>
map<pii,int> mp;
unordered_map<int,int> cx,cy;
I void solve() {
	cin>>n>>m>>K; K=m-K; 
	for(int i=1;i<=n;++i) cin>>c[i].x>>c[i].y,mp[mkp(c[i].x,c[i].y)]=i;
	for(int i=1;i<=m;++i) cin>>o[i].x>>o[i].y;
	for(int i=1;i<=n;++i) stx[c[i].x].insert(c[i].y);
	for(int i=1;i<=n;++i) sty[c[i].y].insert(c[i].x);
	
	int atk=0;
	for(int i=1;i<=n;++i) {
		if(cx[c[i].x]==0) {
			cx[c[i].x]=1;
		} else atk++;
		if(cy[c[i].y]==0) {
			cy[c[i].y]=1;
		} else atk++;
	}
	
	
	for(int i=1;i<=n;++i) add(S,i,1,-1),add(i+n,T,1,-1);
	for(int i=1;i<=m;++i) {
		it nL,nR,nU,nD;
		nR=stx[o[i].x].lower_bound(o[i].y);
		nL=stx[o[i].x].lower_bound(o[i].y);
		nD=sty[o[i].y].lower_bound(o[i].x);
		nU=sty[o[i].y].lower_bound(o[i].x);
		int cnt=0;
		if(nR!=stx[o[i].x].end()) {
			R[i]=mp[mkp(o[i].x,*nR)];
			cnt++;
		}
		if(nR!=stx[o[i].x].begin()) {
			nL--;
			L[i]=mp[mkp(o[i].x,*nL)];
			cnt++;
		}
		if(nD!=sty[o[i].y].end()) {
			D[i]=mp[mkp(*nD,o[i].y)];
			cnt++;
		}
		if(nD!=sty[o[i].y].begin()) {
			nU--;
			U[i]=mp[mkp(*nU,o[i].y)];
			cnt++;
		}
		if(cnt!=4) continue;
		add(R[i],D[i]+n,inf,i); 
	}
	//ck1();
	while(spfa()) {
		memcpy(cur,head,sizeof(cur));
		atk-=2*dfs(S,inf);
	}
	
	int cnt=0;
	for(int i=1;i<=n;++i) {
		if(cnt==K) break;
		for(int j=head[i];j;j=Next[j]) {
			int c=mf[j],u=ver[j];
			if(u>n&&u<=n*2&&c!=inf) {
				cnt++;
				ans[id[j]]=1;
				del[u]=del[i]=1;
				break;
			}
		}
	}
	for(int i=1;i<=m;++i) {
		if(cnt==K||ans[i]) break;
		if(L[i]&&R[i]&&!del[R[i]]) ans[i]=1,cnt++,atk--;
		if(U[i]&&D[i]&&!del[D[i]+n]) ans[i]=1,cnt++,atk--;	
	}
	for(int i=1;i<=m;++i) {
		if(!ans[i]&&cnt<K) cnt++,ans[i]=1;
	}
	cout<<atk<<endl;
	for(int i=1;i<=m;++i) {
		if(!ans[i]) cout<<i<<' ';
	} cout<<endl;
}
I void clear() {
	tot=1; mp.clear(); cx.clear(); cy.clear(); 
	for(int i=1;i<=n*2;++i) head[i]=0; head[S]=head[T]=0;
	for(int i=1;i<=n;++i) stx[c[i].x].clear(),sty[c[i].y].clear();
	for(int i=1;i<=n;++i) ans[i]=L[i]=U[i]=D[i]=R[i]=0;
	for(int i=1;i<=n*2;++i) del[i]=0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int TT; cin>>TT;
	while(TT--) {
		solve();
		clear();
	}
}
/*
1
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


1
3 2 1
10 12
10 10
10 11
1 4
1 5

 
*/
源文件, 语言: C++14

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 26160kb

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
Runtime Error

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
3 4 5 6 7 8 9 
12
3 
8
1 2 3 
0
1 2 3 4 5 6 7 8 9 10 11 12 
0
4 6 7 9 10 11 12 
9
18 19 
1
1 2 3 4 5 6 7 8 
6
5 6 
10
13 14 
1
10 11 12 13 14 15 18 19 20 
0
1 
1
2 3 
0
5 6 7 
11
12 13 14 15 
1
10 11 12 13 14 
4
3 4 5 6 7 8 
1

1
4 
16
1 2 3...

result:
English 繁體中文 简体中文

伺服器時間: 2025-02-08 21:38:35 | 開源專案