QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790820#9810. Obliviate, Then ReincarnateA_J1eWA 0ms3556kbC++172.6kb2024-11-28 15:32:242024-11-28 15:32:35

Judging History

This is the latest submission verdict.

  • [2024-11-28 15:32:35]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3556kb
  • [2024-11-28 15:32:24]
  • 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, vector<array<int, 2>>());
    for (int i = 0; i < m; i ++ ) {
        int u, w, v; cin >> u >> w;
        u = (u % n + n) % n, v = ((u + w) % n + n) % n;
        e[u].push_back({v, w});
    }
    vector<int> num(n), low(n);
    vector<int> scc(n);
    int cnt = 0, dfn = 0;
    stack<int> stk;
    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) {
                auto 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<int> ok(cnt + 1);
    vector<int> vis(cnt + 1);
    vector<int> st(n);
    vector<i64> dist(n);
    function<void(int)> dfs_ = [&] (int u) {
        if (ok[scc[u]]) return ;
        st[u] = 1;
        for (auto [v, w] : e[u]) {
            if (scc[v] != scc[u]) continue;
            if (st[v]) {
                if (dist[v] != dist[u] + w) ok[scc[v]] = 1;
                return ;
            }
            else {
                dist[v] = dist[u] + w;
                dfs_(v);
            }
        }
    };
    for (int i = 0; i < n; i ++ ) {
        if (vis[scc[i]]) continue;
        vis[scc[i]] = 1;
        dfs_(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;
            else g[v].push_back(i);
        }
    }
    function<void()> bfs = [&] () {
        queue<int> que;
        for (int i = 1; i <= cnt; i ++ ) 
            if (ok[i]) que.push(i);
        while (!que.empty()) {
            auto u = que.front(); que.pop();
            for (auto v : g[u]) {
                if (ok[v]) continue;
                ok[v] = 1;
                que.push(v);
            }
        }
    };
    bfs();
    while (q -- ) {
        int u; cin >> u;
        u = (u % n + n) % n;
        cout << (ok[scc[u]] ? "Yes\n" : "No\n");
    }
}

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

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3556kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

No
Yes
Yes

result:

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