QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#685962 | #7738. Equivalent Rewriting | wangcq | WA | 0ms | 3788kb | C++23 | 3.1kb | 2024-10-28 22:15:50 | 2024-10-28 22:15:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-10;
const int N = 100010;
const double PII = acos(-1);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f;
// int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// int dir[8][2] = {{1, 0}, {1, -1}, {1, 1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
// std::mt19937 rng {std::chrono::steady_clock::now().time_since_epoch().count()};
template <typename T>
void debug(T x) {
cerr << x << '\n';
}
template <typename T, typename... Args>
void debug(T x, Args... args) {
cerr << x << ' ';
debug(args...);
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(m + 1);
vector<vector<int>> g(n + 1);
map<int, int> mp;
vector<int> in(n + 1);
for (int i = 1; i <= n; i ++ ) {
int cnt; cin >> cnt;
vector<int> tmp(cnt + 1);
for (int j = 1; j <= cnt; j ++ ) {
int x;
cin >> x;
tmp[j] = x;
a[x] = i;
}
bool ok = 0;
for (int j = 1; j <= cnt; j ++ ) {
if (mp[tmp[j]]) {
// g[i - 1].push_back(i);
ok = 1;
}
}
if (ok) {
g[i - 1].push_back(i);
in[i] ++;
}
mp.clear();
for (int j = 1; j <= cnt; j ++ ) {
mp[tmp[j]] = 1;
}
}
unordered_map<int, int> ump;
int cnt = 0;
for (int i = 1; i <= m; i ++ ) {
// cout << a[i] << " \n"[i == m];
if (ump[a[i]] == 0) cnt ++;
ump[a[i]] = 1;
}
vector<int> ans;
if (cnt < n) {
for (int i = 1; i <= n; i ++ ) {
if (ump[i] == 0) {
ans.push_back(i);
}
}
for (int i = 1; i <= n; i ++ ) {
if (ump[i]) {
ans.push_back(i);
}
}
cout << "Yes" << '\n';
for (int i = 0; i < (int)ans.size(); i ++ ) {
cout << ans[i] << " \n"[i == (int)ans.size() - 1];
}
} else {
queue<int> q;
for (int i = 2; i <= n; i ++ ) {
if (in[i] == 0) {
q.push(i);
}
}
q.push(1);
if (q.size() >= 2) {
while (q.size()) {
auto t = q.front();
ans.push_back(t);
q.pop();
for (auto v : g[t]) {
in[v] --;
if (in[v] == 0) {
q.push(v);
}
}
}
cout << "Yes" << '\n';
for (int i = 0; i < (int)ans.size(); i ++ ) {
cout << ans[i] << " \n"[i == (int)ans.size() - 1];
}
} else {
cout << "No" << '\n';
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
while (T -- ) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
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: 0ms
memory: 3788kb
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:
Yes 1 2 3 4 5 6 7 8 9 10
result:
wrong answer two transactions are same. (test case 1)