QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#291516 | #7744. Elevator | ucup-team963# | RE | 0ms | 0kb | C++14 | 2.3kb | 2023-12-26 20:40:26 | 2023-12-26 20:40:26 |
answer
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e5+10;
int t;
int n,m;
vector < int > e[N];
int a[N];
vector < int > b[N];
map < int , bool > ma;
int In[N];
int Ed[N];
int noww[N],now=0;
int Ans[N],cnt = 0;
#define gc getchar()
int read(){
int s = 0 , f = 0;char ch = gc;
while (ch<'0' || ch>'9') f|=ch == '-' , ch = gc;
while (ch>='0' && ch<='9') s = s*10+ch-48 , ch = gc;
return f?-s:s;
}
bool cmp(int x,int y){
return x>y;
}
void Work(){
cnt = 0;
m = read() , n = read();
for (int i = 1; i <= m; i++){
int X; cin>>X;
for (int j = 1,x; j <= X; j++) x = read(),b[i].pb(x), a[x] = i;
}
for (int i = 1; i <= n; i++) Ed[i] = a[i];
for (int i = 1; i <= m; i++){
ma.clear();
for (int j = 0; j < b[i].size(); j++){
int X = b[i][j];
if (i == Ed[X]) continue;
int x = Ed[X];
if (ma[x]) continue; ma[x] = 1; e[i].pb(x); In[x]++;
}
}
queue < int > q;
for (int i = m; i; i--)
if (In[i] == 0) q.push(i),Ans[++cnt] = i;
while (q.size()){
int x = q.front();
q.pop(); now=0;
for (int i = 0; i < e[x].size(); i++){
int y = e[x][i];
In[y]--;
if (In[y] == 0) q.push(y),noww[++now] = y;
}
if (now == 0) continue;
int Max = 0;
for (int i = 1; i <= now; i++) Max = max(Max,noww[i]);
Ans[++cnt] = Max;
for (int i = 1; i <= now; i++){
if (noww[i] == Max) continue;
Ans[++cnt] = noww[i];
}
now = 0;
}
bool f = 0;
for (int i = 1; i <= m; i++)
if (Ans[i]!=i){f = 1; break;}
if (f == 0) {cout<<"No"<<endl;return;}
cout<<"Yes"<<endl;
for (int i = 1; i <= cnt; i++)
printf("%d ",Ans[i]);
cout<<endl;
return ;
}
int main(){
t = read();
while (t--) Work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
2 4 6 1 1 8 7 2 5 1 1 7 3 2 6 8 1200000 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345 100000 1 100000 100000 1 12345 100000 2 100000 100000 2 12345