QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21022#1814. Kingdoms and QuarantineezoilearnerWA 6ms8496kbC++145.7kb2022-02-24 17:05:572022-05-03 12:19:08

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-03 12:19:08]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：8496kb
查看
  • [2022-02-24 17:05:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define FR first
#define SE second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)

typedef long long ll;
typedef pair<int,int> pii;
#define FR first
#define SE second

inline void rd(int &x){
	x=0;char ch=getchar();int f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}

const int inf=1e9;
int n1,n2,m;
#define Maxn 100010

namespace BUILD{
	int to[Maxn],fr[Maxn],ans[Maxn],cnt=0;
	int zz[Maxn];
	bool odd[Maxn];
	vector<int> vec[Maxn];int at[Maxn],out[Maxn];
	vector<int> g[Maxn];
	bool vis[Maxn];
	void ADD(int id,int s,int t){
		if(s<t)odd[id]=0;else odd[id]=1;
		to[id]=t;fr[id]=s;
		vec[s].push_back(id);out[s]++;
		g[t].push_back(id);
		zz[s]++;zz[t]--;
	}
	int Q[Maxn],hd,tl,sta[Maxn],tp;
	bool tag[Maxn];
	bool cir[Maxn];
	bool FL;
	void add(int x){
		ans[++cnt]=x;
		vis[x]=true;
		cir[x]=true;
		out[fr[x]]--;
		if(!out[fr[x]]&&FL)Q[tl++]=fr[x];
	}
	void solve(){
		FL=true;
		tp=0;sta[0]=-1;
		rep(i,1,n1+n2)
			if(!out[i])Q[tl++]=i;
		int kl=1;
		while(tl<n1+n2){
			if(hd<tl){
				int u=Q[hd];hd++;
				for(int i=0;i<g[u].size();++i)
					if(!vis[g[u][i]]){
						int z=g[u][i];
						vis[z]=true;
						out[fr[z]]--;
						if(!out[fr[z]])Q[tl++]=fr[z];
					}
			}else{
				while(tp&&out[to[sta[tp]]]==0){tag[to[sta[tp]]]=0;tp--;}
				if(tp==0&&sta[0]>0&&out[sta[0]]==0){
					tag[sta[0]]=0;
					sta[0]=-1;
				}
				int y;
				if(tp==0&&sta[0]==-1){
					while(kl<=n1+n2&&out[kl]==0)kl++;
					sta[0]=kl;y=kl;tag[y]=1;
				}else{
					if(!tp)y=sta[0];else y=to[sta[tp]];
				}
				while(true){
					while(at[y]<vec[y].size()&&vis[vec[y][at[y]]])at[y]++;
					sta[++tp]=vec[y][at[y]];
					y=to[vec[y][at[y]]];
					if(tag[y]){
						tp--;int pre=tp+1;
						while(tp&&to[sta[tp]]!=y)tp--;
						if(!odd[sta[pre]]){
							for(int i=pre;i>tp;i-=2)add(sta[i]);
							for(int i=pre-1;i>tp;i-=2)add(sta[i]);
						}else{
							for(int i=pre-1;i>tp;i-=2)add(sta[i]);
							for(int i=pre;i>tp;i-=2)add(sta[i]);
						}
						per(i,pre-1,tp+1)tag[out[sta[i]]]=0;
						break;
					}
					tag[y]=true;
				}
			}
		}
		rep(i,1,m){
			vis[i]=cir[i];
			if(!vis[i]&&to[i])out[fr[i]]++;
		}
		rep(i,1,n1+n2)at[i]=0;
		FL=false;
		hd=tl=0;
		rep(i,1,n1)
			if(zz[i]>0&&out[i]==1)Q[tl++]=i;
		while(hd<tl){
				tp=0;int u=Q[hd];hd++;
				while(out[u]>0){
					while(at[u]<vec[u].size()&&vis[vec[u][at[u]]])at[u]++;
					sta[++tp]=vec[u][at[u]];
					u=to[vec[u][at[u]]];
				}
				for(int j=1;j<=tp;j+=2)add(sta[j]);
				for(int j=2;j<=tp;j+=2)add(sta[j]);
				for(int j=1;j<=tp;j+=2){
					int y=fr[sta[j]];
					if(out[y]==1)Q[tl++]=y;
				}
			}
		printf("%d\n",cnt);
		rep(i,1,cnt)printf("%d ",ans[i]);
		puts("");
	}
}

int head[Maxn],v[Maxn],c[Maxn],w[Maxn],nxt[Maxn],tot=0;
inline void add_edge(int s,int e,int p,int t){
	tot++;v[tot]=e;c[tot]=p;w[tot]=t;nxt[tot]=head[s];head[s]=tot;
	tot++;v[tot]=s;c[tot]=0;w[tot]=-t;nxt[tot]=head[e];head[e]=tot;
}

pii edge[Maxn];
bool type[Maxn];
int deg[Maxn];
int S,T,ns,nt;

int dis[Maxn],D[Maxn];
struct HeapNode{
	int u,d;
	HeapNode(){u=d=0;}
	HeapNode(int _u,int _d){u=_u;d=_d;}
	bool operator <(const HeapNode &p)const {return d>p.d;}
};
priority_queue<HeapNode> Q;
int W=0;
bool DIJ(){
	rep(i,1,T)dis[i]=inf;dis[S]=0;
	Q.push(HeapNode(S,0));
	while(!Q.empty()){
		HeapNode cur=Q.top();Q.pop();
		int u=cur.u;
		if(cur.d!=dis[u])continue;
		for(int i=head[u];i;i=nxt[i])
			if(c[i]){
				int t=dis[u]+D[u]+w[i]-D[v[i]];
				if(t<dis[v[i]]){
					dis[v[i]]=t;
					Q.push(HeapNode(v[i],dis[v[i]]));
				}
			}
	}
	if(dis[T]==inf)return false;
	rep(i,1,T){
		if(dis[i]==inf)D[i]=inf;
		else{
			dis[i]+=D[i];
			D[i]=dis[i];
		}
	}
	return true;
}

int vis[Maxn],visT=0;
int find(int u,int t){
	if(u==T||!t){W+=t*dis[u];return t;}
	vis[u]=visT;
	int res=0;
	for(int i=head[u];i&&t;i=nxt[i])
		if(c[i]&&dis[v[i]]==dis[u]+w[i]&&vis[v[i]]!=visT){
			int cur=find(v[i],min(t,c[i]));
			c[i]-=cur;
			if(i&1)c[i+1]+=cur;else c[i-1]+=cur;
			res+=cur;
			t-=cur;
		}
	return res;
}
void search(){
	while(DIJ()){
		visT++;
		find(S,inf);
	}
}

int main(){
	rd(n1);rd(n2);rd(m);
	ns=n1+n2+1;nt=ns+1;
	S=nt+1;T=nt+2;
	rep(i,1,m){
		rd(edge[i].FR);rd(edge[i].SE);
		type[edge[i].FR]^=1;
		type[edge[i].SE]^=1;
	}
	rep(i,1,m){
		int s=edge[i].FR,t=edge[i].SE;
		if(type[s]==type[t]){
			add_edge(s,t,1,1);
			deg[s]++;deg[t]--;
		}else{
			swap(edge[i].SE,edge[i].FR);
			add_edge(t,s,1,1);
			deg[t]++;deg[s]--;
		}
	}
	int s1=0,s2=0;
	rep(i,1,n1){
		if(deg[i]>0){
			s1+=deg[i]-1;
			if(deg[i]>1)add_edge(S,i,deg[i]-1,0);
			add_edge(ns,i,1,0);
		}else{
			s2-=deg[i];
			add_edge(i,nt,1,0);
			if(deg[i]<0)add_edge(i,T,-deg[i],0);
		}
	}
	rep(i,n1+1,n1+n2){
		if(deg[i]>=0){
			s1+=deg[i];
			if(deg[i]>0)add_edge(S,i,deg[i],0);
			add_edge(ns,i,1,0);
		}else{
			s2-=deg[i]+1;
			add_edge(i,nt,1,0);
			if(deg[i]<-1)add_edge(i,T,-deg[i]-1,0);
		}
	}
	add_edge(nt,ns,inf,0);
	add_edge(ns,T,s1,0);
	add_edge(S,nt,s2,0);
	search();
	rep(i,1,m)
		if(c[(i-1)*2+1])BUILD::ADD(i,edge[i].FR,edge[i].SE);
	BUILD::solve();
	return 0;
}/*
2 3 5
1 3
1 4
1 5
2 4
2 5

4 3 7
1 5
2 5
2 6
2 7
3 6
4 5
4 7

10 10 20
2 11
2 17
1 12
8 14
9 15
10 12
9 13
1 18
3 15
2 14
2 16
7 13
8 15
8 20
9 12
6 13
8 16
6 11
4 20
6 16

10 10 30
8 18
9 12
10 19
10 14
2 16
1 11
6 13
1 18
4 12
9 13
4 20
8 16
2 20
5 20
7 14
3 15
5 18
2 12
4 15
5 17
4 18
5 19
7 17
3 16
7 19
8 19
1 19
10 18
10 12
3 18

*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 8488kb

input:

2 3 5
1 3
1 4
1 5
2 4
2 5

output:

3
4 1 2

result:

ok accepted

Test #2:

score: 0
Accepted
time: 0ms
memory: 8396kb

input:

1 2 2
1 2
1 3

output:

0

result:

ok accepted

Test #3:

score: 0
Accepted
time: 0ms
memory: 8464kb

input:

4 3 7
1 5
2 5
2 6
2 7
3 6
4 5
4 7

output:

5
2 7 4 6 1

result:

ok accepted

Test #4:

score: 0
Accepted
time: 1ms
memory: 8492kb

input:

10 10 20
2 11
2 17
1 12
8 14
9 15
10 12
9 13
1 18
3 15
2 14
2 16
7 13
8 15
8 20
9 12
6 13
8 16
6 11
4 20
6 16

output:

11
20 1 11 18 10 9 14 13 16 5 6

result:

ok accepted

Test #5:

score: 0
Accepted
time: 2ms
memory: 8468kb

input:

10 10 30
8 18
9 12
10 19
10 14
2 16
1 11
6 13
1 18
4 12
9 13
4 20
8 16
2 20
5 20
7 14
3 15
5 18
2 12
4 15
5 17
4 18
5 19
7 17
3 16
7 19
8 19
1 19
10 18
10 12
3 18

output:

21
25 4 15 3 26 17 1 22 9 13 18 11 19 24 16 20 2 28 6 8 27

result:

ok accepted

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 8496kb

input:

10 10 50
10 12
3 20
7 20
8 19
5 17
6 16
10 13
10 15
3 15
4 17
4 19
9 19
10 16
1 17
9 18
3 17
6 11
8 12
8 20
9 11
6 20
2 14
6 12
7 11
5 15
7 15
7 17
10 18
5 18
4 12
4 18
7 16
4 20
10 19
1 18
7 12
8 16
8 11
2 18
8 13
2 19
1 16
8 17
6 19
9 15
2 12
10 11
6 14
2 11
7 14

output:

19
3 17 21 24 23 22 36 48 37 12 25 6 4 45 19 15 8 28 13

result:

wrong answer wrong answer, we can do more operations
English 繁體中文 简体中文

Server Time: 2024-11-30 00:48:19 | OpenSource Project