QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#919#592157#7777. Intro: Dawn of a New EranodgdNKheyuxiangSuccess!2024-09-26 21:17:282024-09-26 21:17:28

详细

Extra Test:

Time Limit Exceeded

input:

20000
11 616074294 616688586 617543956 617804057 616760371 617032967 615806357 615831200 615673205 616467136 616604322
16 354544692 355221295 356256699 354712646 356303283 356124582 356079479 355539739 354375681 356232106 355579703 355195290 354556796 355032840 354752514 356006391
13 246406187 50522...

output:


result:


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;
}