QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689785#7738. Equivalent Rewritingi_love_qingyu#WA 2ms7916kbC++202.0kb2024-10-30 18:38:292024-10-30 18:38:38

Judging History

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

  • [2024-10-30 18:38:38]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7916kb
  • [2024-10-30 18:38:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int book[100005],last[100005],ans[100005],head[100005],cnt,d[2000006],sum,g[100005];
struct node{
    int y,next;
}e[500005];
void add(int x,int y){
    e[++cnt].y=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int x){
    sum++;
    for(int i=head[x];i;i=e[i].next)
        if(!book[e[i].y]){
            book[e[i].y]=1;
            dfs(e[i].y);
        }
}
int main()
{
    
    int t;
    cin>>t;
    while(t--){
        int n,m,p=0;cnt=0;
        cin>>m>>n;
        vector<vector<int > > d(m+1);
        for(int i=1;i<=n;i++)last[i]=0;
        for(int i=1;i<=m;i++)ans[i]=i,head[i]=book[i]=0;
        for(int i=1;i<=m;i++){
            int k;
            cin>>k;
            d[i].resize(k+1);
            d[i][0] = k;
            for(int j=1;j<=k;j++){
                cin>>d[i][j];
                last[d[i][j]]=i;
            }
            sort(d[i].begin()+1,d[i].end());
        }
        cnt=0;
        for(int i=1;i<=m;i++){
            int k=d[i][0];;
            for(int j=1;j<=k;j++)
                if(last[d[i][j]]!=i)
                    add(i,last[d[i][j]]);
        }
        book[1]=1;
        sum=0;
        dfs(1);
        if(sum!=m){
            for(int i=2;i<=n;i++)
                if(book[i]!=book[i-1]){
                    int q=0;
                    for(int l=1,r=1;l<=d[i-1][0]&&r<=d[i][0];)
                        if(d[i-1][l]>d[i][r])r++;
                        else if(d[i-1][l]<d[i][r])l++;
                        else {
                            if(last[d[i][r]]==i){q=1;break;}
                            l++,r++;
                        }
                    if(!q){
                        swap(ans[i],ans[i-1]);
                        break;
                    }
            }
            cout<<"Yes"<<endl;
            for(int i=1;i<=m;i++)
                cout<<ans[i]<<" ";
            cout<<endl;
        }
        else cout<<"No"<<endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7692kb

input:

3
3 6
3 3 1 5
2 5 3
2 2 6
2 3
3 1 3 2
2 3 1
1 3
2 2 1

output:

Yes
1 3 2 
No
No

result:

ok OK. (3 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 7916kb

input:

1
10 5
2 2 4
4 1 3 4 2
1 2
3 2 1 4
4 5 2 4 3
3 2 5 4
3 5 4 2
3 1 3 2
5 1 4 2 3 5
1 4

output:

Yes
2 1 3 4 5 6 7 8 9 10 

result:

ok OK. (1 test case)

Test #3:

score: 0
Accepted
time: 0ms
memory: 7688kb

input:

1
20 5
5 4 1 2 5 3
2 5 3
3 5 1 2
5 4 5 1 3 2
3 4 2 5
5 3 1 5 4 2
5 5 1 2 3 4
1 3
4 5 1 2 3
4 4 1 3 5
2 5 2
4 2 3 5 1
3 2 4 5
5 2 3 4 1 5
4 5 2 4 3
1 2
2 4 3
4 4 5 3 1
5 4 1 5 3 2
3 5 1 3

output:

Yes
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

result:

ok OK. (1 test case)

Test #4:

score: 0
Accepted
time: 1ms
memory: 7684kb

input:

1
40 10
2 4 1
10 5 8 2 3 6 7 4 1 10 9
3 10 9 7
1 9
10 10 5 6 9 2 8 3 1 4 7
7 8 4 7 5 2 3 6
5 2 6 5 1 10
6 6 5 4 8 7 1
3 4 9 8
9 9 10 4 2 1 8 7 5 3
2 5 7
9 8 6 1 2 9 7 5 10 3
2 8 1
8 8 3 10 9 1 4 5 6
2 3 4
5 5 3 6 2 7
10 3 2 8 9 10 1 7 4 6 5
2 1 9
1 1
3 3 7 4
5 2 6 5 7 1
7 3 2 4 9 10 6 1
1 4
5 6 4 5 ...

output:

Yes
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 

result:

ok OK. (1 test case)

Test #5:

score: 0
Accepted
time: 1ms
memory: 7912kb

input:

1
100 20
12 10 5 11 13 12 14 7 15 19 18 3 1
10 16 11 19 8 10 15 5 12 13 14
12 16 8 11 15 2 18 14 13 20 4 12 7
10 3 9 1 7 19 6 2 14 8 20
7 17 18 20 3 9 6 10
4 1 4 19 9
13 14 17 16 11 13 8 10 19 18 7 5 20 1
13 10 15 3 2 9 1 17 7 20 13 19 18 16
2 17 9
10 20 19 13 14 16 17 8 12 18 15
5 2 16 14 6 19
1 14...

output:

Yes
2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 

result:

ok OK. (1 test case)

Test #6:

score: -100
Wrong Answer
time: 2ms
memory: 6008kb

input:

1
5000 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1...

output:

Yes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...

result:

wrong answer two transactions are same. (test case 1)