QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246480 | #7738. Equivalent Rewriting | LZX_OVO# | WA | 2ms | 11836kb | C++14 | 2.7kb | 2023-11-10 20:55:30 | 2023-11-10 20:55:32 |
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;
}
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<=n;i++){
head[i] = 0;
}
for(int i = 1;i<=m;i++){
nums[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++){
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(i == errid)continue;
cout<< " " << i ;
}
cout << "\n";
return;
}
if(dfs(1) == true){
cout << "Yes" <<'\n';
cout << "1";
for(int i = 2;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();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 11832kb
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: 11836kb
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)