QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291516#7744. Elevatorucup-team963#RE 0ms0kbC++142.3kb2023-12-26 20:40:262023-12-26 20:40:26

Judging History

你现在查看的是最新测评结果

  • [2023-12-26 20:40:26]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: