QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789787#9810. Obliviate, Then ReincarnateA_J1eWA 1ms4072kbC++172.9kb2024-11-27 21:52:022024-11-27 21:52:05

Judging History

This is the latest submission verdict.

  • [2024-11-27 21:52:05]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4072kb
  • [2024-11-27 21:52:02]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
    int n, m, q; cin >> n >> m >> q;
    vector e(n + 1, vector<array<int, 2>>());
    for (int i = 1; i <= m; i ++ ) {
        int u, x, v; cin >> u >> x;
        u = (u % n + n) % n, v = ((u + x) % n + n) % n;
        e[u].push_back({v, x});
    }
    stack<int> stk;
    int cnt, dfn;
    vector<int> low(n + 1), num(n + 1);
    vector<int> scc_(n + 1);
    function<void(int)> dfs = [&] (int u) {
        stk.push(u);
        low[u] = num[u] = ++ dfn;
        for (auto [v, w] : e[u]) {
            if (!num[v]) {
                dfs(v);
                low[u] = min(low[v], low[u]);
            }
            else if (!scc_[v]) {
                low[u] = min(low[u], num[v]);
            }
        }
        if (low[u] == num[u]) {
            cnt ++;
            while (1) {
                int v = stk.top();
                stk.pop();
                scc_[v] = cnt;
                if (u == v) break;
            }
        }
    };
    function<void()> tarjan = [&] () {
        for (int i = 0; i < n; i ++ ) {
            if (!num[i]) dfs(i);
        }
    };
    tarjan();
    vector<i64> dist(n + 1);
    vector<int> ok(cnt + 1);
    vector<int> st(n + 1);
    function<void(int, int)> dfs_ = [&] (int u, int c) {
        if (ok[c]) return ;
        st[u] = 1;
        for (auto [v, w] : e[u]) {
            if (scc_[v] != c) continue;
            if (!st[v]) {
                dist[v] = dist[u] + w;
                dfs_(v, c);
            }
            else {
                if (dist[v] != dist[u] + w) 
                    ok[c] = 1;
                return ;
            }
        }
    };
    vector<int> vis(cnt + 1);
    for (int i = 0; i < n; i ++ ) {
        if (vis[scc_[i]]) continue;
        vis[scc_[i]] = 1;
        dfs_(i, scc_[i]);
    }
    vector g(cnt + 1, vector<int>());
    for (int i = 0; i < n; i ++ ) {
        for (auto [v, w] : e[i]) {
            if (scc_[v] == scc_[i]) continue;
            g[v].push_back(i);
        }
    }
    function<void()> bfs = [&] () {
        queue<int> q;
        for (int i = 1; i <= cnt; i ++ ) 
            if (ok[i]) q.push(i);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : g[u]) {
                if (!ok[scc_[v]]) {
                    ok[scc_[v]] = 1;
                    q.push(scc_[v]);
                }
            }
        }
    };
    bfs();
    for (int i = 0; i < n; i ++ ) 
        cout << scc_[i] << " " << i << " " << ok[scc_[i]] << "\n";
    while (q -- ) {
        int u; cin >> u;
        u = (u % n + n) % n;
        cout << (ok[scc_[u]] ? "Yes\n" : "No\n");
    }
}

signed main (void) {
    ios::sync_with_stdio();
    cin.tie(0); cout.tie(0);
    int T = 1;
    while (T -- ) solve();
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4072kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

32586 0 0
32588 1 0
32587 2 1
No
Yes
No

result:

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