QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#276577#7733. Cool, It’s Yesterday Four Times Moredoyo#WA 28ms143040kbC++142.1kb2023-12-05 23:03:142023-12-05 23:03:14

Judging History

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

  • [2023-12-05 23:03:14]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:143040kb
  • [2023-12-05 23:03:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
stack<int>s[200010];
int n,m,cnt;
struct Edge
{
    int next;int to;
}edge[maxn];
int ru[maxn],tops[maxn],head[maxn];
void init(){
    for(int i=1;i<=n;++i)
        while(!s[i].empty())s[i].pop();
    for(int i=1;i<=m;i++) head[i]=0,ru[i]=0,tops[i]=0;
    for(int i=1;i<=cnt;i++) edge[i].next=0;
    cnt=0;
}

void addedge(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
queue<int> q;
struct node
{
    int id;int tops;
}a[maxn];
void topsort()
{
    for(int i=1;i<=m;i++)
        if(ru[i]==0) q.push(i),tops[i]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(tops[v]) continue;
            ru[v]--;
            if(!ru[v]) q.push(v),tops[v]=tops[u]+1;
        }
    }
}
bool cmp(node x,node y)
{
    if(x.tops==y.tops) return x.id>y.id;
    return x.tops<y.tops;
}
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(0);
	int T;cin>>T;
	while(T--){

        cin>>m>>n;
        for(int i=1;i<=m;++i){
            int p;cin>>p;
            for(int j=1;j<=p;++j){
                int t;cin>>t;
                s[t].push(i);
            }
        }
        for(int i=1;i<=n;++i){
            if(!s[i].empty()){
                int u=s[i].top();
                s[i].pop();
                while(!s[i].empty()){
                    addedge(s[i].top(),u);
                    ru[u]++;
                    s[i].pop();
                }
            }
        }

        topsort();
        for(int i=1;i<=m;i++)
        {
            a[i].id=i;a[i].tops=tops[i];
        }
        sort(a+1,a+m+1,cmp);
        bool ansflag=false;
        for(int i=1;i<m;i++)
            if(a[i+1].tops==a[i].tops) ansflag=true;
        if(ansflag)
        {
            cout<<"Yes\n";
            for(int i=1;i<=m;i++) cout<<a[i].id<<((i==m)?'\n':' ');
        }
        else cout<<"No\n";
        init();
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 28ms
memory: 143040kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

Yes
2 1
Yes
2 1
Yes
2 1
Yes
2 1

result:

wrong answer 1st lines differ - expected: '3', found: 'Yes'