QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#795889#9810. Obliviate, Then Reincarnateucup-team4435#WA 206ms20864kbC++203.4kb2024-12-01 03:21:522024-12-01 03:21:52

Judging History

This is the latest submission verdict.

  • [2024-12-01 03:21:52]
  • Judged
  • Verdict: WA
  • Time: 206ms
  • Memory: 20864kb
  • [2024-12-01 03:21:52]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

template<typename Fun>
struct y_combinator {
    const Fun fun;

    explicit y_combinator(const Fun&& fun) : fun(std::forward<const Fun>(fun)) {}

    template<typename... Args>
    auto operator()(Args&&... args) const {
        return fun(std::ref(*this), std::forward<Args>(args)...);
    }
};

class strongly_connected_components {
private:
    int n;
    std::vector<std::vector<int>> g;

    int cur_id, cur_scc;
    std::vector<int> id, f, scc, st;

    void dfs(int v) {
        st.push_back(v);
        id[v] = f[v] = cur_id++;

        for (auto u : g[v]) {
            if (id[u] == -1) {
                dfs(u);
                f[v] = std::min(f[v], f[u]);
            } else if (scc[u] == -1) {
                f[v] = std::min(f[v], id[u]);
            }
        }

        if (id[v] == f[v]) {
            int u;
            do {
                u = st.back();
                st.pop_back();
                scc[u] = cur_scc;
            } while (u != v);
            cur_scc++;
        }
    }

public:
    strongly_connected_components(int n = 0) : n(n), g(n) {}

    // Adds directed edge (from -> to)
    void add(int from, int to) {
        g[from].push_back(to);
    }

    // Returns for each vertex the scc index from [0, number_of_scc).
    // If u is reachable from v, then scc_index[v] <= scc_index[u].
    std::vector<int> solve() {
        cur_id = cur_scc = 0;
        id.assign(n, -1);
        f.assign(n, -1);
        scc.assign(n, -1);

        for (int v = 0; v < n; v++) {
            if (id[v] == -1) {
                dfs(v);
            }
        }

        for (auto &x : scc) {
            x = cur_scc - 1 - x;
        }
        return scc;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<pair<int, int>>> g(n);
    strongly_connected_components scc(n);

    auto mod = [&](int x) {
        return (x % n + n) % n;
    };

    while (m--) {
        int a, b;
        cin >> a >> b;
        a = mod(a);
        int nxt = mod(a + b);
        g[a].emplace_back(nxt, b);
        scc.add(a, nxt);
    }

    auto comp = scc.solve();
    const int C = *max_element(all(comp)) + 1;
    vector<vector<int>> comps(C);
    for (int v = 0; v < n; v++) {
        comps[comp[v]].push_back(v);
    }

    vector<bool> good(C), used(n);
    vector<ll> val(n);

    for (int i = 0; i < C; i++) {
        bool valid = true;

        y_combinator([&](auto dfs, int v) -> void {
            used[v] = true;
            for (auto [u, w] : g[v]) {
                if (!used[u]) {
                    val[u] = val[v] + w;
                    dfs(u);
                } else if (val[u] != val[v] + w) {
                    valid = false;
                }
            }
        })(comps[i][0]);

        good[i] = !valid;
    }

    for (int i = C - 1; i >= 0; i--) {
        for (auto v : comps[i]) {
            for (auto [u, _] : g[v]) {
                if (good[comp[u]]) {
                    good[i] = true;
                }
            }
        }
    }

    while (q--) {
        int x;
        cin >> x;
        x = mod(x);
        cout << (good[comp[x]] ? "Yes" : "No") << '\n';
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3616kb

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: 1ms
memory: 3608kb

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Wrong Answer
time: 206ms
memory: 20864kb

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:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer 70268th words differ - expected: 'No', found: 'Yes'