QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#276577 | #7733. Cool, It’s Yesterday Four Times More | doyo# | WA | 28ms | 143040kb | C++14 | 2.1kb | 2023-12-05 23:03:14 | 2023-12-05 23:03:14 |
Judging History
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'