QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789496#9810. Obliviate, Then ReincarnatexhytomTL 747ms3832kbC++233.4kb2024-11-27 20:34:322024-11-27 20:34:32

Judging History

This is the latest submission verdict.

  • [2024-11-27 20:34:32]
  • Judged
  • Verdict: TL
  • Time: 747ms
  • Memory: 3832kb
  • [2024-11-27 20:34:32]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::pair<int, int>> edges(m);
    vector<vector<pair<int,int>>> adj(n);
    vector<vector<pair<int,int>>> bac(n);

    std::map<std::pair<int, int>, int> is;

    std::vector<int> cnt(n + 1);

    for (auto &[a, b] : edges) {
        cin >> a >> b;
        a = (a % n + n) % n;
        int u = a, v = u + b;
        int w = 0;
        w = v / n;
        v += v / n * n;

        while (v < 0) {
            v += n;
            w += 1;
        }

        while (v >= n) {
            v -= n;
            w -= 1;
        }

        std::cerr << "?" << u << " " << v << " " << w << std::endl;
        if (!is.count({u, v})) {
            is[{u, v}] = w;
        } else if(is[{u, v}] != w) {
            is[{u, v}] = 1E18;
        }
        bac[v].push_back({u, w});
    }

    for (auto [tmp, w] : is) {
        auto [u, v] = tmp;
        if (w == 1E18) {
            adj[u].push_back({v, 1E18});
        } else {
            adj[u].push_back({v, w});
        }
    }

    std::vector<int> vis(n, -1E18), cur(n, -1E18);
    std::vector<int> ok(n, 0);

    for (int i = 0; i < n; i++) {

        if (vis[i] == -1E18) {

            auto dfs = [&](auto self, int x, int fx, int d, int all) -> void {
                vis[x] = 1;
                cur[x] = d;
                cnt[x] = all;
                // std::cerr << "DFS" << x << " " << fx << " " << d << std::endl;
                for (auto [y, w] : adj[x]) {
                    if (vis[y] == -1E18) {
                        if (w == 1E18) {
                            self(self, y, x, 1E18, all + 1);
                        } else {
                            self(self, y, x, d + w, all);
                        }

                    } else {
                        std::cerr << "!!!" << x << " " << y << " " << cur[x] << " " << cur[y] << " " <<  d << " " << w << std::endl;;
                        if ((cur[y] != -1E18 && (cur[y] != d + w || w == 1E18)) || (cnt[x] - cnt[y])) {
                            std::cerr << "TRUE" << std::endl;
                            ok[y] = true;
                        }


                    }
                    ok[x] |= ok[y];
                }
                cur[x] = -1E18;

            };
            dfs(dfs, i, -1, 0, 0);
        }
        std::cerr << "####" << std::endl;
        for (int i = 0; i < n; i++) {
            std::cerr << vis[i] << " \n"[i == n - 1];
        }
        for (int i = 0; i < n; i++) {
            std::cerr << ok[i] << " \n"[i == n - 1];
        }
    }

    std::queue<int> que;
    for (int i = 0; i < n; i++) {
        if (ok[i]) {
            que.push(i);
        }
    }

    while (!que.empty()) {
        int x = que.front();
        que.pop();

        for (auto [y, w] : bac[x]) {
            if (!ok[y]) {
                ok[y] = true;
                que.push(y);
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        int x;
        std::cin >> x;
        x = (x % n + n) % n;

        std::cout << (ok[x] ? "Yes" : "No") << "\n";
    }



}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    // std::cin >> t;

    while (t --) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 747ms
memory: 3536kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 492ms
memory: 3528kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Time Limit Exceeded

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: