QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#819866#9810. Obliviate, Then ReincarnateljljljljWA 6ms17760kbC++202.3kb2024-12-18 17:51:082024-12-18 17:51:08

Judging History

This is the latest submission verdict.

  • [2024-12-18 17:51:08]
  • Judged
  • Verdict: WA
  • Time: 6ms
  • Memory: 17760kb
  • [2024-12-18 17:51:08]
  • Submitted

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
vector<pii> tu[1001000];
vector<int> tu1[1001000];
const int N = 1e6 + 10;
int low[N], dfn[N], vis[N], be[N], ok[N], sum[N];
int total, cnt, inde;
stack<int> st;
int flag;
void tarjan(int x) {
    dfn[x] = low[x] = ++total;
    vis[x] = 1;
    st.push(x);
    for (auto e : tu[x]) {
        if (!dfn[e.first]) {
            tarjan(e.first);
            low[x] = min(low[e.first], low[x]);
        } else if (vis[e.first] == 1) {
            low[x] = min(low[x], dfn[e.first]);
        }
    }
    if (dfn[x] == low[x]) {
        int v;
        inde = inde + 1;
        do {
            v = st.top();
            st.pop();
            be[v] = inde;
            vis[v] = 0;

        } while (v != x);
    }
}
void dfs(int u) {
    vis[u] = 1;
    for (auto [v, w] : tu[u]) {
        if (be[v] != be[u])
            continue;
        if (vis[v]) {
            if (sum[v] != sum[u] + w)
                ok[v] = 1;
        } else {
            sum[v] = sum[u] + w;
            dfs(v);
        }
    }
}
void dfs1(int u) {
    vis[u] = 1;
    for (int x : tu1[u])
        if (!vis[x])
            dfs1(x);
    ok[u] = 1;
}
void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        int temp = (x % n + n) % n;
        int temp2 = ((x + y) % n + n) % n;
        int val = y;
        tu[temp].push_back({temp2, val});
        tu1[temp2].push_back(temp);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i])
            tarjan(i);
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && ok[i]) {
            dfs1(i);
        }
    }
    while (q--) {
        int temp;
        cin >> temp;
        temp = ((temp % n) + n) % n;
        cout << (ok[temp] == 1 ? "Yes\n" : "No\n");
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    // while (1)
    //     ;
}

詳細信息

Test #1:

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

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: 6ms
memory: 16808kb

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

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

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