QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246527 | #7738. Equivalent Rewriting | LZX_OVO# | WA | 2ms | 13696kb | C++14 | 2.4kb | 2023-11-10 21:43:28 | 2023-11-10 21:43:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 2000005
struct EDGE{
int to , nt;
}edge[N*2];
int cnt;
int head[N];
int k[N];
int in[N];
int out[N];
void add_edge(int u , int v){
edge[++cnt] = {v , head[u]};
head[u] = cnt;
};
set<pair<int,int> >st;
int ans[N];
int anscnt = 1;
int n , m , frontk_cnt , numtmp;
void dfs(int id){
vector<int>add_ans;
for(int i = head[id];i; i = edge[i].nt){
int v = edge[i].to;
if((--in[v]) == 0 ){
add_ans.push_back(v);
}
}
sort(add_ans.begin() , add_ans.end()) ;
reverse(add_ans.begin() , add_ans.end());
for(auto x : add_ans){
ans[++anscnt ] = x;
}
for(auto x : add_ans){
dfs(x);
}
}
void solve(){
cin >> n >> m;
for(int i = 1;i<=n;i++){
in[i] = 0;
out[i] = 0;
head[i] = 0;
}
for(int i = 1;i<=m;i++){
k[i] = 0;
}
st.clear();
cnt = 0;
for(int i = 1;i<=n;i++){
cin >> frontk_cnt;
for(int j = 1;j<=frontk_cnt;j++){
cin >> numtmp;
if(k[numtmp] == 0) {
k[numtmp] = i;
}else{
if(st.find(make_pair(k[numtmp] , i)) == st.end()){
add_edge(k[numtmp] , i);
st.insert(make_pair(k[numtmp] , i));
out[k[numtmp]] ++;
in[i] ++ ;
}
k[numtmp] = i;
}
}
}
//是否有唯一起点
for(int i = 1;i<=n;i++){
if((in[i] == 0) && (i != 1)){
//输出
cout << "Yes" << "\n";
cout << i ;
for(int j = 1;j<=n;j++){
if(j!=i){
cout << " " << j;
}
}
cout <<"\n";
return;
}
}
ans[1] = 1;
dfs(1);
bool flag = 0;
for(int i = 1;i<=n;i++){
if(ans[i] != i){
flag = 1;
}
}
if(flag == 1){
cout << "Yes" << "\n";
for(int i = 1; i<=n;i++){
if(i == 1){
cout << 1;
}else{
cout << " " << i ;
}
}
cout << "\n";
}else{
cout << "No" << "\n";
}
}
int main(){
int t; cin >> t;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13696kb
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: 2ms
memory: 13684kb
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)