QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#916 | #592157 | #7777. Intro: Dawn of a New Era | nodgd | NKheyuxiang | Failed. | 2024-09-26 21:08:39 | 2024-09-26 21:08:39 |
Details
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 | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}