QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783394#9810. Obliviate, Then ReincarnatecddRE 0ms3820kbC++233.9kb2024-11-26 09:33:002024-11-26 09:33:01

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 09:33:01]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 3820kb
  • [2024-11-26 09:33:00]
  • Submitted

answer

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

#define int long long

typedef pair<int, int> pii;
typedef long long LL;
typedef unsigned long long uLL;

const int inf32 = 1e9;
const LL inf64 = 1e18;

struct SCC {
    int n;
    vector<vector<int>> G;
    vector<int> dfn, low, ins, stk;
    vector<int> col, siz;
    int id, colcnt;

    SCC() {}
    SCC(int x) {
        init(x);
    }
    void init(int x) {
        n = x;
        G.assign(n + 5, {});
    }
    void add_edge(int x, int y) {
        G[x].push_back(y);
    }
    void dfs(int cur) {
        dfn[cur] = low[cur] = ++id;
        stk.push_back(cur), ins[cur] = 1;
        for (auto v : G[cur]) {
            if (!dfn[v]) {
                dfs(v);
                low[cur] = min(low[cur], low[v]);
            } else if (ins[v]) {
                low[cur] = min(low[cur], dfn[v]);
            }
        }
        
        if (dfn[cur] == low[cur]) {
            ++colcnt;
            int x = stk.back();
            while (x != cur) {
                col[x] = colcnt;
                ins[x] = 0;
                ++siz[colcnt];
                stk.pop_back();
                x = stk.back();
            }
            col[cur] = colcnt;
            ins[cur] = 0;
            ++siz[colcnt];
            stk.pop_back();
        }
    }
    void gets() {
        dfn.assign(n + 5, 0);
        low.assign(n + 5, 0);
        ins.assign(n + 5, 0);
        col.assign(n + 5, 0);
        siz.assign(n + 5, 0);
        stk.clear();
        id = colcnt = 0;

        for (int i = 0; i < n; i++)
            if (!dfn[i]) dfs(i);
    }
    int diff(int x, int y) {
		return col[x] != col[y];
	}
};

signed main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        int n, k, Q;
        cin >> n >> k >> Q;
        
        SCC TG(n);
        vector<vector<pii>> G(n + 5);
        vector<pii> e;
        for (int i = 1; i <= k; i++) {
            int x, y;
            cin >> x >> y;
            int u = (x % n + n) % n, v = (u + y) % n, w = y;
            // cerr << u << ' ' << v << ' ' << w << endl;

            G[u].push_back({v, w});
            TG.add_edge(u, v);
            e.push_back({u, v});
        }

        TG.gets();

        int len = TG.colcnt;
        vector<int> vis(len + 5, 0), ff(len + 5, 0), val(n + 5, inf64);
        function<int(int, int, int, int)> dfs = [&] (int cur, int ftr, int now, int s) -> int {
            // cerr << cur << ' ' << s << ' ' << val[cur] << endl;
            if (val[cur] != inf64) {
                return s != val[cur];
            }
            val[cur] = s;

            for (auto [v, w] : G[cur]) {
                if (TG.col[v] != now) continue;
                if (dfs(v, cur, now, s + w)) return 1;
            }
            return 0;
        };

        for (int i = 0; i < n; i++) {
            int col = TG.col[i];
            if (vis[col]) continue;
            vis[col] = 1;
            ff[col] = dfs(i, 0, col, 0);
        }

        vector<pii> l;
        for (auto [u, v] : e) {
            if (TG.col[u] == TG.col[v]) continue;
            l.push_back({u, v});
        }

        sort(l.begin(), l.end(), [&](pii x, pii y) {
            if (x.first != y.first) return x.first > y.first;
            return x.second > y.second;
        });

        for (auto [u, v] : l) {
            u = TG.col[u], v = TG.col[v];
            // cerr << u <<' ' << v << endl;
            ff[u] = max(ff[u], ff[v]);
        }

        // for (int i = 0; i < n; i++) cerr << TG.col[i] << ' '; cerr << endl;
        // for (int i = 1; i <= len; i++) cerr << ff[i] << ' '; cerr << endl;

        while (Q--) {
            int x;
            cin >> x;
            x = (x % n + n) % n;
            cout << (ff[TG.col[x]] ? "Yes\n" : "No\n");
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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