QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#343819 | #7738. Equivalent Rewriting | ucup-team992# | WA | 1ms | 3496kb | C++20 | 1.8kb | 2024-03-03 05:37:08 | 2024-03-03 05:37:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef int uci;
#define int long long
#define ll long long
#define ar array
void solve(){
int n, m;
cin >> n >> m;
vector<vector<int>> a(n);
vector<set<int>> adj(n);
vector<vector<int>> vals(m);
for(int i{}; i < n; ++i){
int p;
cin >> p;
for(int j{}; j < p; ++j){
int t;
cin >> t;
t--;
vals[t].push_back(i);
}
}
vector<int> deg(n);
for(int i{}; i < m; ++i){
if(vals[i].size() > 1){
for(int j{}; j < vals[i].size()-1; ++j){
if(!adj[vals[i].back()].count(vals[i][j])){
deg[vals[i][j]]++;
adj[vals[i].back()].insert(vals[i][j]);
}
}
}
}
priority_queue<int, vector<int>, greater<>> pq;
vector<int> out;
vector<bool> taken(n);
for(int i{}; i < n; ++i){
if(deg[i] == 0){
pq.push(i);
taken[i] = true;
}
}
while(pq.size()){
int v = pq.top();
pq.pop();
out.push_back(v);
for(int j : adj[v]){
deg[j]--;
if(!taken[j] && deg[j] == 0){
pq.push(j);
}
}
}
reverse(out.begin(), out.end());
if(out.size() == n){
for(int i{}; i < n; ++i){
if(out[i] != i){
cout << "YES\n";
for(int j : out)
cout << j+1 << ' ';
cout << '\n';
return;
}
}
}
cout << "NO\n";
}
uci main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for(int i{}; i<t; ++i)
solve();
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3496kb
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:
wrong answer Token parameter [name=yesno] equals to "YES", doesn't correspond to pattern "Yes|No" (test case 1)