QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#919 | #592157 | #7777. Intro: Dawn of a New Era | nodgd | NKheyuxiang | Success! | 2024-09-26 21:17:28 | 2024-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 Era | NKheyuxiang | TL | 846ms | 245064kb | C++14 | 2.8kb | 2024-09-26 20:59:13 | 2024-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;
}