QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#658166 | #7738. Equivalent Rewriting | Detach# | WA | 7ms | 55000kb | C++20 | 2.4kb | 2024-10-19 16:17:36 | 2024-10-19 16:17:37 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #include <algorithm>
// #include <queue>
// #include <map>
// #include <iostream>
// #include <string>
// #include <set>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using LL = long long;
using PII = pair<int, int>;
using i128 = __int128_t;
using ULL = unsigned long long;
using Tree = tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update>;
constexpr int INF = 0x3f3f3f3f, MOD = 1e9 + 7, N = 1e6 + 5, M = 1e6 + 5;
constexpr LL LINF = 0x3f3f3f3f3f3f3f3f;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m;
int x,y;
vector<int> v[N];
set<int> g[N];
int mx[N];
int d[N];
void solve(){
cin>>n>>m;
rep(i,1,n){
int x;
cin>>x;
rep(_,1,x){
cin>>y;
mx[y]=i;
v[i].pb(y);
}
}
// rep(i,1,m){
// cout<<i<<" "<<mx[i]<<endl;
// }
rep(i,1,n){
for(int x : v[i]){
if(mx[x]==i) continue;
if(g[i].count(mx[x])) continue;
g[i].insert(mx[x]);
// cout<<i<<" "<<x<<" "<<mx[x]<<endl;
d[mx[x]]++;
}
}
// rep(i,1,n){
// cout<<i<<": ";
// for(int x : g[i]){
// cout<<x<<" ";
// }
// cout<<endl;
// }
priority_queue<int> q;
vector<int> ans;
rep(i,1,n) if(d[i]==0) q.emplace(i);
while(!q.empty()){
int u=q.top();q.pop();
ans.pb(u);
for(int v : g[u]){
if(--d[v]==0) q.emplace(v);
}
}
int idx=1;
for(int x : ans){
if(x==idx++){
cout<<"No\n";
return;
}
}
cout<<"Yes\n";
rep(i,0,n-1){
cout<<ans[i];
if(i!=n-1) cout<<" ";
}
cout<<endl;
rep(i,1,n) v[i].clear(),g[i].clear();
rep(i,1,n) d[i]=0;
}
signed main()
{
// (.*) "$1"
// freopen("park.in", "r", stdin);
// freopen("park.out", "w", stdout);
// cout << fixed << setprecision(2);
// srand(NULL);
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1;
cin >> T;
while(T -- )
solve();
// fclose(stdin);
// fclose(stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 55000kb
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: 5ms
memory: 54760kb
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)