QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785558#9810. Obliviate, Then Reincarnateucup-team3519#RE 0ms3740kbC++172.3kb2024-11-26 18:15:022024-11-26 18:15:05

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 18:15:05]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 3740kb
  • [2024-11-26 18:15:02]
  • Submitted

answer

#include <bits/stdc++.h>

using i64 = int64_t;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<std::vector<std::pair<int, int>>> adj(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        std::cin >> a >> b;
        a = (a % n + n) % n;

        adj[a].emplace_back(((a + b) % n + n) % n, b);
    }

    std::vector<int> stk;
    std::vector<int> dfn(n, -1), low(n), bel(n, -1);
    int cur = 0, cnt = 0;

    std::vector<uint8_t> ok(n);
    std::vector<i64> dep(n);
    auto dfs = [&](auto &self, int x) -> void {
        dfn[x] = low[x] = cur++;
        stk.push_back(x);
        for (auto [to, w] : adj[x]) {
            if (dfn[to] == -1) {
                dep[to] = dep[x] + w;
                self(self, to);
                low[x] = std::min(low[x], low[to]);
            } else if (bel[to] == -1) {
                low[x] = std::min(low[x], dfn[to]);
                if (dep[x] - dep[to] + w) {
                    ok[x] = true;
                }
            }
        }
        if (dfn[x] == low[x]) {
            int y;
            do {
                y = stk.back();
                bel[y] = cnt;
                stk.pop_back();
            } while (y != x);
            ++cnt;
        }
    };

    for (int i = 0; i < n; ++i) {
        if (dfn[i] == -1) dfs(dfs, i);
    }

    int tot = *std::max_element(bel.begin(), bel.end()) + 1;
    std::vector<uint8_t> bok(tot);
    for (int i = 0; i < n; ++i) {
        if (ok[i]) bok[bel[i]] = true;
    }

    std::vector<uint8_t> vist(tot);
    std::vector<std::vector<int>> G(tot);
    for (int i = 0; i < n; ++i) {
        for (auto [to, w] : adj[i]) {
            G[bel[i]].push_back(bel[to]);
        }
    }
    auto get = [&](auto &self, int x) -> bool {
        if (vist[x] || bok[x]) return bok[x];
        vist[x] = true;
        for (int to : G[x]) {
            if (self(self, to)) {
                bok[x] = true;
                break;
            }
        }
        return bok[x];
    };
    
    while (q--) {
        int x;
        std::cin >> x;
        x = (x % n + n) % n;
        if (get(get, x)) std::cout << "Yes\n";
        else std::cout << "No\n";
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3604kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

Yes
Yes
No

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Runtime Error

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:


result: