QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789649#9810. Obliviate, Then ReincarnateA_J1eRE 0ms0kbC++232.5kb2024-11-27 21:19:232024-11-27 21:19:30

Judging History

This is the latest submission verdict.

  • [2024-11-27 21:19:30]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2024-11-27 21:19:23]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int 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);
    vector<vector<int>> scc;
    vector<int> t(1);
    scc.push_back(t);
    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 ++;
            vector<int> sc;
            while (1) {
                int v = stk.top();
                stk.pop();
                scc_[v] = cnt;
                sc.push_back(v);
                if (u == v) break;
            }
            scc.push_back(sc);
        }
    };
    function<void()> tarjan = [&] () {
        for (int i = 1; i <= n; i ++ ) {
            if (!num[i]) dfs(i);
        }
    };
    tarjan();
    vector<int> 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 ;
            }
        }
    };
    for (int i = 1; i <= cnt; i ++ ) {
        int u = scc[i].back();
        dist[u] = 0;
        dfs_(u, i);
    }
    for (int i = 1; i <= n; i ++ ) {
        if (ok[scc_[i]]) continue;
        for (auto [v, w] : e[i]) {
            if (ok[scc_[v]]) {
                ok[scc_[i]] = 1;
                break;
            }
        }
    }
    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
Runtime Error

input:

3 2 3
1 1
-1 3
1
2
3

output:


result: