QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#881237#9810. Obliviate, Then ReincarnateUESTC_NLNSWA 1ms3712kbC++202.8kb2025-02-04 13:57:232025-02-04 13:57:24

Judging History

This is the latest submission verdict.

  • [2025-02-04 13:57:24]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3712kb
  • [2025-02-04 13:57:23]
  • Submitted

answer

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using pii = pair<int, int>;
struct solver {
    int n, m, q;
    vector<int> dfn, low, stk, id;
    vector<vector<pii>> g;
    vector<vector<int>> ig;
    vector<int> bl;
    vector<int> tag;
    vector<int> vis;
    vector<int> dis;
    int cur = 0, cnt = 0;

    solver(int n) : n(n), dis(n + 1), tag(n + 1), ig(n + 1),
                    dfn(n + 1), g(n + 1), bl(n + 1),
                    low(n + 1), stk(), id(n + 1, -1), vis(n + 1) {}

    void tarjan(int u) {
        dfn[u] = low[u] = cur++;
        stk.push_back(u);
        for (const auto [v, w] : g[u]) {
            if (dfn[v] == 0)
                tarjan(v), low[u] = min(low[u], low[v]);
            else if (id[v] == -1)
                low[u] = min(low[u], low[v]);
        }
        if (dfn[u] == low[u]) {
            int v;
            do {
                v = stk.back();
                id[v] = cnt;
                stk.pop_back();
            } while (v != u);
            cnt++;
        }
    }

    bool check(int u) {
        vis[u] = 1;
        for (const auto [v, w] : g[u]) {
            if (id[v] != id[u]) continue;
            int nd = dis[u] + w;
            if (!vis[v]) {
                dis[v] = nd;
                if (check(v)) return 1;
            } else {
                if (nd != dis[v]) {
                    return 1;
                }
            }
        }
        return 0;
    }

    void fan() {
        queue<int> q;
        for (int i = 0; i < n; ++i)
            if (tag[i]) q.push(i);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (const auto v : ig[u]) {
                if (!tag[v]) tag[v] = 1, q.push(v);
            }
        }
    }

    int norm(int x) {
        return (x % n + n) % n;
    }

    void solve() {
        cin >> m >> q;
        for (int i = 0; i < m; ++i) {
            int x, w, y;
            cin >> x >> w;
            x = norm(x), y = norm(x + w);
            if (x == y) {
                if (w) tag[x] = 1;
            } else {
                g[x].push_back({y, w});
                ig[y].push_back(x);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (dfn[i] == 0) {
                tarjan(i);
                tag[i] = check(i);
            }
        }
        fan();
        for (int i = 0; i < q; ++i) {
            int u;
            cin >> u;
            u = norm(u);
            cout << (tag[u] ? "Yes" : "No") << '\n';
        }
    }
};
int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n;
    cin >> n;
    solver s(n);
    s.solve();
}
/*
3 3 3
1 1
2 -2
3 4
1
2
3

*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

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: 3712kb

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3712kb

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

wrong answer 1st words differ - expected: 'Yes', found: 'No'