QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#916#592157#7777. Intro: Dawn of a New EranodgdNKheyuxiangFailed.2024-09-26 21:08:392024-09-26 21:08:39

详细

Extra Test:

Accepted
time: 1215ms
memory: 230756kb

input:

100000
2 5133 4551
2 8873 13905
2 16895 9092
2 18036 17939
2 10385 8455
2 10515 10242
2 5343 9491
2 18212 16191
2 14481 15198
2 19076 19423
2 14971 15987
2 5692 8273
2 14403 16840
2 17730 14989
2 3666 1229
2 9085 8082
2 2191 6310
2 9287 9727
2 9802 5161
2 2412 3966
2 15900 10882
2 15790 13806
2 9155...

output:

99054
235 8906 12109 56241 98855 73990 87254 62032 11448 42957 24731 7112 92560 37070 40309 1422 52586 65906 22612 72473 61100 49141 98217 14327 75276 67968 70084 99326 17774 41450 69748 13832 147 89938 32776 85654 33661 87471 11566 99829 28753 23261 90972 31053 61306 77818 59196 13578 55640 58761 6...

result:

ok correct!

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#592157#7777. Intro: Dawn of a New EraNKheyuxiangTL 846ms245064kbC++142.8kb2024-09-26 20:59:132024-10-13 20:51:47

answer

#include<bits/stdc++.h>
#define N 300005
using namespace std;
const int inf=1e9;
int n,rk[N],mx[N],srt[N],m;
struct node{
	int mx,id;
}p[N];
bool cmp(node p1,node p2){
	return p1.mx<p2.mx;
}
vector<int > a[N];
int h[N],to[N*5],nxt[N*5],w[N*5],cnt;
void jb(int u,int v,int W){
	w[++cnt]=W;
	to[cnt]=v;
	nxt[cnt]=h[u];
	h[u]=cnt;
}
void JB(int u,int v,int W){
	jb(u,v,W);
	jb(v,u,0);
}
int dis[N],ct[N],cur[N],k,s,t;
int dfs(int u,int fl){
	if(u==t) return fl;
	int dl=0;
	for(int &i=cur[u];i!=0;i=nxt[i]){
		int v=to[i];
		if(dis[v]+1==dis[u]&&w[i]){
			int tmp=dfs(v,min(w[i],fl-dl));
			w[i]-=tmp;
			w[i^1]+=tmp;
			dl+=tmp;
			if(dl==fl) return dl;
		}
	}
	cur[u]=h[u];
	ct[dis[u]]--;
	if(ct[dis[u]]==0) dis[s]=k+1;
	ct[++dis[u]]++;
	return dl;
}
int work(){
	for(int i=1;i<=k;i++) cur[i]=h[i];
	int res=0;
	ct[0]=k;
	while(dis[s]<=k) res+=dfs(s,inf);
	return res;
}
int id1[N],id2[N],vct[N];
int ansnxt[N],nop[N],lstp[N];
queue<int > q[N];
bool nox[N];
int main(){
	cnt=1;
	scanf("%d",&n);
	for(int i=1,j,o;i<=n;i++){
		scanf("%d",&j);
		while(j--){
			scanf("%d",&o);
			a[i].push_back(o);
			srt[++m]=o;
		}
	}
	sort(srt+1,srt+m+1);
	m=unique(srt+1,srt+m+1)-srt-1;
	for(int i=1;i<=n;i++){
		int len=a[i].size();
		for(int j=0;j<len;j++){
			a[i][j]=lower_bound(srt+1,srt+m+1,a[i][j])-srt;
			mx[i]=max(mx[i],a[i][j]);
		}
		p[i].mx=mx[i];p[i].id=i;
	}
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;i++) vct[p[i].mx]++;
	s=n+1,t=k=n+2;
	for(int i=1;i<=n;i++){
		JB(s,i,1);
		if(i>1&&p[i].mx==p[i-1].mx) JB(i,id2[p[i].mx],1);
		else{
			if(vct[p[i].mx]==1){
				id1[p[i].mx]=++k;
				JB(id1[p[i].mx],t,1);
			}
			else{
				id1[p[i].mx]=++k;
				id2[p[i].mx]=++k;
				JB(id2[p[i].mx],id1[p[i].mx],vct[p[i].mx]-1);
				JB(id1[p[i].mx],t,vct[p[i].mx]);
				JB(i,id2[p[i].mx],1);
			}
		}
		for(int v:a[p[i].id])
			if(v!=p[i].mx&&id1[v]) JB(i,id1[v],1);
	}
	printf("%d\n",work());
	for(int u=1;u<=n;u++){
		int toid=-1;
		for(int i=h[u];i!=0;i=nxt[i]){
			int v=to[i];
			if(v!=s&&w[i]==0) toid=v;
		}
		if(toid!=id2[p[u].mx])
			q[id1[p[u].mx]].push(u);
	}
	for(int u=1;u<=n;u++){
		int toid=-1;
		for(int i=h[u];i!=0;i=nxt[i]){
			int v=to[i];
			if(v!=s&&w[i]==0) toid=v;
		}
		if(toid==id2[p[u].mx]) continue;
		if(toid!=-1){
			ansnxt[q[toid].front()]=u;
			q[toid].pop();
		}
		lstp[p[u].mx]=u;
	}
	for(int u=1;u<=n;u++){
		int toid=-1;
		for(int i=h[u];i!=0;i=nxt[i]){
			int v=to[i];
			if(v!=s&&w[i]==0) toid=v;
		}
		if(toid==id2[p[u].mx]){
			ansnxt[u]=ansnxt[lstp[p[u].mx]];
			ansnxt[lstp[p[u].mx]]=u;
			lstp[p[u].mx]=u;
		}
	}
	for(int i=1;i<=n;i++)
		if(ansnxt[i]!=0) nox[ansnxt[i]]=1;
	for(int i=1;i<=n;i++){
		if(nox[i]) continue;
		printf("%d ",p[i].id);
		int x=ansnxt[i];
		while(x!=0){
			printf("%d ",p[x].id);
			x=ansnxt[x];
		}
	}
	return 0;
}