QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#874164#8593. Cointatyam0 0ms3712kbC++261.1kb2025-01-27 17:39:442025-01-27 17:39:44

Judging History

你现在查看的是最新测评结果

  • [2025-01-27 17:39:44]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:3712kb
  • [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%