QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#914#547115#7777. Intro: Dawn of a New EranodgdskcFailed.2024-09-26 21:04:412024-09-26 21:04:42

详细

Extra Test:

Accepted
time: 1280ms
memory: 35432kb

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
99887 3529 16465 5826 45949 52785 58021 72825 4822 12749 28966 46149 15877 7905 23076 28218 57879 91001 65007 14362 84487 93865 43279 54014 62952 74011 84453 38706 1749 25060 97003 20319 6966 18286 22215 54409 88881 58757 59274 60493 35065 27707 62255 96982 26349 86403 28843 29767 82030 85044 ...

result:

ok correct!

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547115#7777. Intro: Dawn of a New EraskcAC ✓393ms45744kbC++143.1kb2024-09-04 18:22:072024-10-13 20:51:30

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=100000,M=200000;
constexpr int tN=N*3+1,tM=N+M+N*3+N*2;
vector<int> vec[N+10];
int n,val[N+10],vtop;
int getid(int x){
	int rv=lower_bound(val+1,val+1+vtop,x)-val;
	if(val[rv]==x) return rv;
	return -1;
}
struct EDGE{
	int to,next,w;
}e[tM*2+20];
int head[tN+10],etop,headc[tN+10];
void adde(int u,int v,int w){
	e[etop].to=v;
	e[etop].next=head[u];
	e[etop].w=w;
	head[u]=etop++;
}
void add(int u,int v,int w){
	adde(u,v,w);
	adde(v,u,0);
}
int dis[tN+10],vis[tN+10];
deque<int> q;
void bfs(int x){
	memset(dis,63,sizeof(dis));
	dis[x]=0;
	q.push_back(x);
	int i;
	while(!q.empty()){
		x=q.front();
		q.pop_front();
		for(i=head[x];~i;i=e[i].next){
			if(!e[i^1].w) continue;
			if(dis[e[i].to]>dis[x]+1){
				dis[e[i].to]=dis[x]+1;
				q.push_back(e[i].to);
			}
		}
	}
}
int dfs(int s,int t,int w){
	if(s==t) return w;
	vis[s]=1;
	int b=w,tmp;
	for(int &i=head[s];~i;i=e[i].next){
		if(!e[i].w) continue;
		if(vis[e[i].to]) continue;
		if(dis[e[i].to]!=dis[s]-1) continue;
		tmp=dfs(e[i].to,t,min(w,e[i].w));
		w-=tmp;
		e[i].w-=tmp;
		e[i^1].w+=tmp;
		if(!w) break;
	}
	vis[s]=0;
	return b-w;
}
int Dinic(int s,int t){
	memcpy(headc,head,sizeof(head));
	int sum=0,flow;
	while(1){
		bfs(t);
		if(dis[s]>=1e7) break;
		sum+=flow=dfs(s,t,(int)1e9);
		memcpy(head,headc,sizeof(head));
	}
	return sum;
}
int b[N+10],btop,abab[tM*2+10];
void dfs(int x){
	if(1<=x&&x<=n) b[++btop]=x;
	if(x==tN) return;
	for(int&i=head[x];~i;i=e[i].next){
		if(abab[i]!=1){
			if(!e[i^1].w) continue;
			if(vis[e[i].to]) continue;
			if(i&1) continue;
			if(abab[i]==2) continue;
		}
		--e[i^1].w;
		dfs(e[i].to);
		break;
	}
}
int nxt[N+10],vval[N+10],vvis[N+10];
int main(){
	memset(head,255,sizeof(head));
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	int i;
	for(i=1;i<=n;++i){
		int k;
		cin>>k;
		vec[i].resize(k);
		for(int j=0;j<k;++j) cin>>vec[i][j];
		sort(vec[i].begin(),vec[i].end());
		val[++vtop]=vec[i].back();
	}
	sort(val+1,val+1+vtop);
	vtop=unique(val+1,val+1+vtop)-val-1;
	val[vtop+1]=1e9;
	for(i=1;i<=n;++i){
		add(i,n+getid(vec[i].back()),1);
		for(auto j:vec[i]){
			int o=getid(j);
			if(o!=-1&&j!=vec[i].back()){
				add(n+vtop+o,i,1);
			}
		}
	}
	for(i=1;i<=vtop;++i){
		add(n+i,tN+2,1);
		add(tN+1,n+vtop+i,1);
		add(n+i,n+vtop+i,n);
		abab[etop-2]=1;
		abab[etop-1]=2;
	}
	for(i=1;i<=n;++i){
		add(0,i,1);
	}
	for(i=1;i<=vtop;++i){
		add(n+vtop+i,tN,1);
	}
	add(tN,0,n);
	int tmp=Dinic(tN+1,tN+2);
	assert(tmp==vtop);
	tmp=e[etop-1].w;
	vis[tN+1]=vis[tN+2]=1;
	e[etop-2].w=e[etop-1].w=0;
	tmp-=Dinic(tN,0);
	cout<<n-tmp<<'\n';
	for(int i=0;i<n;++i){
		dfs(0);
	}
	static bool vvis[tN+10];
	static vector<int>V[tN+10];
	for(int i=1;i<=btop;++i){
		vvis[b[i]]=1;
	}
	for(int i=1;i<=n;++i)
		if(!vvis[i])V[getid(vec[i].back())].emplace_back(i);
	for(int i=1;i<=btop;++i){
		cout<<b[i]<<' ';
		auto&v=V[getid(vec[b[i]].back())];
		for(int x:v)cout<<x<<' ';
		v.clear();
	}
	for(int i=1;i<=vtop;++i)
		for(int x:V[i])
			cout<<x<<' ';
	cout<<'\n';
	return 0;
}