QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693821 | #7738. Equivalent Rewriting | Rosmontis_L# | RE | 1ms | 3560kb | C++20 | 1.6kb | 2024-10-31 16:48:04 | 2024-10-31 16:48:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PLL;
const ll N = 100010;
vector<ll> edge[N], p[N];
ll teg[N];
void solve(){
ll n, m;
cin >> n >> m;
for(int i = 1; i <= m; i ++){
edge[i].clear();
p[i].clear();
teg[i] = 0;
}
for(int i = 1; i <= n; i ++){
ll siz;
cin >> siz;
for(int j = 1; j <= siz; j ++){
ll x;
cin >> x;
p[x].push_back(i);
}
}
for(int i = 1; i <= n; i ++){
for(int j = 0; j < p[i].size() - 1; j ++){
edge[p[i][j]].push_back(p[i].back());
teg[p[i].back()] ++;
}
}
vector<ll> ans(n + 10);
ll sum = 0, now = 0;
for(int i = n; i >= 1; i --){
if(teg[i] != 0) continue;
priority_queue<ll> q;
q.push(i);
while(q.size()){
auto u = q.top();
q.pop();
ans[++ now] = u;
for(auto v : edge[u]){
if(-- teg[v] == 0) q.push(v);
}
}
}
bool ok = 1;
for(int i = 1; i <= n; i ++){
if(ans[i] != i){
ok = 0;
break;
}
}
if(ok){
cout << "No\n";
return;
}
cout << "Yes\n";
for(int i = 1; i <= n; i ++){
cout << ans[i] << " \n"[i == n];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
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
Runtime Error
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