QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#874164 | #8593. Coin | tatyam | 0 | 0ms | 3712kb | C++26 | 1.1kb | 2025-01-27 17:39:44 | 2025-01-27 17:39:44 |
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, M;
cin >> N >> M;
vector g(N, vector<int>{});
for (int _ : views::iota(0, M)) {
int a, b;
cin >> a >> b;
a--; b--;
g[a].push_back(b);
}
auto topo = [&](auto cmp) {
vector<int> indeg(N);
vector<int> order;
for (auto& v : g) for (int i : v) indeg[i]++;
priority_queue<int, vector<int>, decltype(cmp)> q;
for (int i : views::iota(0, N)) if (indeg[i] == 0) q.push(i);
while (size(q)) {
int i = q.top(); q.pop();
order.push_back(i);
for (int j : g[i]) if (--indeg[j] == 0) q.push(j);
}
return order;
};
auto order1 = topo(greater<int>());
auto order2 = topo(less<int>());
vector<int> ans(N, -1);
if (size(order1) == N) for (int i : views::iota(0, N)) {
if (order1[i] != order2[i]) continue;
ans[order1[i]] = i + 1;
}
for (int i : ans) cout << i << ' ';
cout << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Acceptable Answer
time: 0ms
memory: 3712kb
input:
4 4 2 4 3 1 4 1 2 3
output:
4 1 -1 -1
result:
points 0.50 -1 correct
Test #2:
score: 3
Acceptable Answer
time: 0ms
memory: 3712kb
input:
6 8 1 5 5 4 6 2 2 5 4 3 6 1 6 5 2 1
output:
3 2 6 5 4 1
result:
points 0.50 -1 correct
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3712kb
input:
2 1 1 2
output:
1 2
result:
wrong answer wa
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%