QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789650#9810. Obliviate, Then ReincarnateA_J1eWA 0ms3792kbC++232.5kb2024-11-27 21:20:052024-11-27 21:20:06

Judging History

This is the latest submission verdict.

  • [2024-11-27 21:20:06]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3792kb
  • [2024-11-27 21:20:05]
  • 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);
    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 0ms
memory: 3544kb

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

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