QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#546788 | #7738. Equivalent Rewriting | pzc2004# | WA | 6ms | 34640kb | C++14 | 1.5kb | 2024-09-04 13:41:06 | 2024-09-04 13:41:06 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i=l, _=r; i<=_; ++i)
using namespace std;
template<class T>inline void read(T &x){
x=0;
char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+(c&15),c=getchar();
}
const int mN=1e5+9, mS=1.1e6+9;
int n, m, ind[mS];
vector<int> a[mN], ver[mS], ans;
int sta[mS], top;
// bool vis[mS];
bool check() {
rep(i, 1, n) {
if(ans[i-1]==i) {
return 0;
}
}
return 1;
}
int main(){
int T_T;
read(T_T);
while(T_T--) {
rep(i, 1, m) {
a[i].clear();
}
rep(i, 1, m+n) {
ver[i].clear();
}
rep(i, 1, n+m) {
ind[i]=0;
// vis[i]=0;
}
ans.clear();
top=0;
read(n), read(m);
rep(i, 1, n) {
int pi, id;
scanf("%d", &pi);
rep(__, 1, pi) {
read(id);
a[id].push_back(i);
}
}
rep(i, 1, m) if(a[i].size()>1) {
rep(__, 0, a[i].size()-2) {
ver[a[i][__]].push_back(n+i);
++ind[n+i];
}
ver[n+i].push_back(a[i].back());
++ind[a[i].back()];
}
rep(i, 1, m+n) if(!ind[i]) {
sta[++top]=i;
// vis[i]=1;
}
while(top>0) {
int tmp=sta[top];
if(tmp==ans.size()+1 && top>1) {
swap(sta[top], sta[1]);
}
int x=sta[top--];
if(x<=n) {
ans.push_back(x);
}
for(int y: ver[x]) {
--ind[y];
if(!ind[y]) {
sta[++top]=y;
}
}
}
if(check()) {
puts("Yes");
for(int x: ans) {
printf("%d ", x);
}
puts("");
} else {
puts("No");
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 34640kb
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: 4ms
memory: 32396kb
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)