QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#594946 | #7738. Equivalent Rewriting | zhangboju# | WA | 1ms | 6156kb | C++14 | 1.9kb | 2024-09-28 11:28:48 | 2024-09-28 11:28:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
struct edge {
int v,nxt;
}e[MAXN<<1];
int n,m,sz,cnt,tot;
int pre[MAXN],h[MAXN],ind[MAXN],ans[MAXN];
queue<int> q;
void output() {
for(int i=n;i;i--) {
printf("%d ",ans[i]);
}
puts("");
}
void addedge(int u,int v) {
e[++cnt].v=v;
e[cnt].nxt=h[u];
h[u]=cnt;
ind[v]++;
}
void solve() {
cin>>n>>m;
for(int i=1;i<=n;i++) {
int k;
scanf("%d",&k);
while(k--) {
int x;
scanf("%d",&x);
if(pre[x]) {
addedge(i,pre[x]);
}
pre[x]=i;
}
}
for(int i=1;i<=n;i++) {
if(ind[i]==0) {
q.push(i);
sz++;
}
}
bool flag=0;
while(!q.empty()) {
if(sz>1) {
flag=1;
int u=q.front();
q.pop();
int v=q.front();
q.pop();
if(u<v) {
q.push(u);
q.push(v);
}
else {
q.push(v);
q.push(u);
}
}
int u=q.front();
ans[++tot]=u;
sz--;
q.pop();
for(int i=h[u];i;i=e[i].nxt) {
int v=e[i].v;
ind[v]--;
if(!ind[v]) {
q.push(v);
sz++;
}
}
}
if(flag) {
puts("Yes");
output();
}
else {
puts("No");
}
return ;
}
void clear() {
for(int i=1;i<=n;i++) {
ans[i]=ind[i]=h[i]=0;
}
for(int i=1;i<=m;i++) {
pre[i]=0;
}
while(!q.empty()) {
q.pop();
}
sz=n=m=cnt=tot=0;
}
int main() {
int t;
cin>>t;
while(t--) {
solve();
clear();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6156kb
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 3 1 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3956kb
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:
No
result:
wrong answer jury found an answer but participant did not (test case 1)