QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#270347 | #7738. Equivalent Rewriting | Godwang# | WA | 3ms | 13284kb | C++17 | 2.3kb | 2023-11-30 19:32:12 | 2023-11-30 19:32:14 |
Judging History
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);
}
printf("Yes\n");
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: 100
Accepted
time: 0ms
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:
Yes 3 1 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 13284kb
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 8 9 10 8 9 10 8 9 10 8 9 10 8 9 10 8 9 10 8 9 10 1
result:
wrong answer output is not a permutation. (test case 1)