QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789790#9810. Obliviate, Then ReincarnateA_J1eRE 0ms3596kbC++172.9kb2024-11-27 21:55:242024-11-27 21:55:26

Judging History

This is the latest submission verdict.

  • [2024-11-27 21:55:26]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 3596kb
  • [2024-11-27 21:55: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 + 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 = 0, dfn = 0;
    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> que;
        for (int i = 1; i <= cnt; i ++ ) 
            if (ok[i]) que.push(i);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (auto v : g[u]) {
                if (!ok[scc_[v]]) {
                    ok[scc_[v]] = 1;
                    que.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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Runtime Error

input:

50134 500000 500000
-154428638 -283522863
-186373509 -327130969
154999046 46750274
-933523447 349415487
-437683609 140099255
864996699 -262318199
811293034 -264299324
120273173 52410685
874944410 -52048424
445049930 -803690605
-138111276 -104634331
720288580 126597671
471164416 -348777147
-356502322...

output:


result: