QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#270345#7738. Equivalent RewritingGodwang#WA 2ms13208kbC++172.3kb2023-11-30 19:30:472023-11-30 19:30:48

Judging History

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

  • [2023-11-30 19:30:48]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:13208kb
  • [2023-11-30 19:30:47]
  • 提交

answer

#include<cstdio>
#include<vector>
#include<cstring>
#include<set>
using namespace std;
int r[100001];
vector<int> p[100001];
vector<int> mu[100001];
set<int> a[100001];
int pl[100001];
inline bool nosolution(int n,int m)
{
        bool realno=true;
        for (int i=1;i<=n-1;++i)
                realno=realno && (a[i].size()==1 && a[i].count(i+1)==1);
        return realno;
}
bool book[100001];
void dfs(int x,int cnt,vector<vector<int> > &ans)
{
        book[x]=true;
        ans[cnt].push_back(x);
        if (a[x].count(x+1)==1) dfs(x+1,cnt,ans);
}
int main()
{
        int t,ti;
        //freopen("input.in","r",stdin);
        scanf("%d",&t);
        for (ti=1;ti<=t;++ti)
        {
        int n,m,i,j,t1;
        scanf("%d%d",&n,&m);
        for (i=1;i<=m;++i)
                {
                r[i]=0;
                mu[i].clear();
                a[i].clear();
                }
        for (i=1;i<=n;++i)
                {
                p[i].clear();
                book[i]=false;
                scanf("%d",&pl[i]);
                p[i].resize(pl[i]);
                for (j=0;j<pl[i];++j)
                        {
                        scanf("%d",&p[i][j]);
                        r[p[i][j]]=i;
                        mu[p[i][j]].push_back(i);
                        }
                }
        for (i=1;i<=m;++i)
                {
                if (mu[i].empty()) continue;
                const int x=mu[i].back();
                for (auto j:mu[i])
                        if (j!=x) a[j].insert(x);
                }
        if (nosolution(n,m))
                {
                printf("No\n");
                continue;
                }
        int cnt=0;
        vector<vector<int> > ans;
        ans.emplace_back();
        for (i=1;i<=n;++i)
                if (book[i]==false)
                        {
                        ++cnt;
                        ans.emplace_back();
                        dfs(i,cnt,ans);
                        }
        for (i=2;i<=cnt;++i)
                for (auto x:ans[cnt])
                        printf("%d ",x);
        for (auto x:ans[1])
                if (x!=ans[1].back()) printf("%d ",x);
                        else printf("%d",x);
        printf("\n");
        }
        return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 13208kb

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:

3 1 2
No
No

result:

wrong answer Token parameter [name=yesno] equals to "3", doesn't correspond to pattern "Yes|No" (test case 1)