QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#685914 | #7738. Equivalent Rewriting | wangcq | WA | 0ms | 3648kb | C++23 | 2.2kb | 2024-10-28 21:56:32 | 2024-10-28 21:56:37 |
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<vector<int>> e(m + 1);
vector<int> in(n + 1);
for (int i = 1; i <= n; i ++ ) {
int cnt; cin >> cnt;
for (int j = 1; j <= cnt; j ++ ) {
int x;
cin >> x;
e[x].push_back(i);
}
}
map<int, set<int>> g;
for (int i = 1; i <= m; i ++ ) {
for (int j = 0; j < (int)e[i].size() - 1; j ++ ) {
int t = g[e[i][j]].size();
g[e[i][j]].insert(e[i][j + 1]);
if ((int)g[e[i][j]].size() == t + 1) {
in[e[i][j + 1]] ++;
}
}
}
bool ok = 0;
queue<int> q;
for (int i = 2; i <= n; i ++ ) {
if (in[i]) {
} else {
ok = 1;
q.push(i);
}
}
q.push(1);
if (! ok) {
cout << "No" << '\n';
} else {
vector<int> ans;
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';
int m = ans.size();
for (int i = 0; i < m; i ++ ) {
cout << ans[i] << " \n"[i == m - 1];
}
}
}
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: 3600kb
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: 3648kb
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)