QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#246384 | #7738. Equivalent Rewriting | LZX_OVO# | WA | 2ms | 13888kb | C++14 | 2.7kb | 2023-11-10 19:38:54 | 2023-11-10 19:38:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int nums[2000005];
struct EDGE{
int to, nt;
}edge[4000005];
int head[2000005];
int in[2000005];
int out[2000005];
int cnt = 0;
void add_edge(int u , int v ){
edge[++cnt] = {v , head[u]};
head[u] = cnt;
}
int ans[2000005];
set<pair<int ,int> >st;
int anspos= 0;
int ansval =0;
int n , m , opnum , tmppos;
bool dfs(int id){
if(id == m+1){
return false;
}
int nextid = id+1;
int ret = false;
for(int i = head[id] ; i ; i=edge[i].nt){
int v = edge[i].to;
if(--in[v] == 0){
if(nextid == v){
continue;
}else{
anspos = nextid;
ansval = v;
ret = 1;
break;
}
}
}
if(ret){
return true;
}else{
return dfs(nextid);
}
}
void solve(){
anspos= 0;
ansval =0;
st.clear();
cnt = 0;
cin >> n >> m;
for(int i = 1;i<=m;i++){
nums[i] = 0;
head[i] = 0;
}
for(int i = 1;i<=n;i++){
cin >> opnum;
for(int j = 1;j<=opnum;j++){
cin >> tmppos;
if(nums[tmppos] == 0){
nums[tmppos] = i;
}else{
int be = nums[tmppos];
int af = i;
if(st.find(make_pair(be , af)) == st.end()) {
add_edge(be , af);
st.insert(make_pair(be , af));
//cout << "add_edge" << be <<" " << af << endl;
in[af]++;
out[be]++;
}
nums[tmppos] = af;
}
}
}
//拓扑
int errid = 0;
for(int i = 1;i<=n;i++){
ans[i] = i;
}
for(int i = 1;i<=n;i++){
if(in[i] == 0){
if(i != 1){
errid = i;
break;
}
}
}
if(errid != 0){
cout << "Yes" <<'\n';
cout << errid << " ";
for(int i = 1;i<=n;i++){
if(ans[i] == errid)continue;
cout << ans[i] << " ";
}
cout << "\n";
return;
}
if(dfs(1) == true){
cout << "Yes" <<'\n';
for(int i = 1;i<=n;i++){
if(i == ansval ){
continue;
}
if(i == anspos){
cout << ansval << " ";
}
cout << i <<" ";
}
cout << "\n";
}else{
cout << "No" << '\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 13868kb
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: 13888kb
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)