QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#800802#9810. Obliviate, Then Reincarnateucup-team5008WA 3ms8360kbC++233.3kb2024-12-06 15:46:212024-12-06 15:46:27

Judging History

This is the latest submission verdict.

  • [2024-12-06 15:46:27]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 8360kb
  • [2024-12-06 15:46:21]
  • Submitted

answer

#include <bits/stdc++.h>
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); i--)
#define rrep(i, n) rrep2(i, n, 0)
#define all(a) a.begin(), a.end()
#define SZ(a) ll(a.size())
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
const ll inf = LLONG_MAX / 4;
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#define int long long

const int N = 500005;
std::vector<int> tr[N], cmp_g[N];
std::vector<std::pair<int, int> > g[N];
int n, m, q, cmp[N], ord[N];
long long dep[N];
bool gone[N], cyc[N], u[N];

int z(int x) {
	x %= n;
	x += n;
	return x % n;
}

class SCC {
    int n;
    vvl G;
    vl ord, low;
    stack<int> st;

    void dfs(int u, int &k) {
        ord[u] = low[u] = k++;
        st.push(u);
        for (int v: G[u]) {
            if (ord[v] == -1) {
                dfs(v, k);
                chmin(low[u], low[v]);
            } else {
                chmin(low[u], ord[v]);
            }
        }
        if (low[u] == ord[u]) {
            while (true) {
                int now = st.top();
                st.pop();
                ord[now] = inf;
                id[now] = num;
                if (now == u) break;
            }
            ++num;
        }
    }

public:
    // number of components
    int num;
    vl id;
    vvl scc_list;

    SCC(vvl G) : G(G) {
        n = G.size();
        ord.assign(n, -1);
        low.resize(n);
        id.resize(n);
        num = 0;
        int k = 0;
        rep(i, n) if (ord[i] == -1) dfs(i, k);
        vl cnt(num);
        rep(i, n) {
            id[i] = num - 1 - id[i];
            ++cnt[id[i]];
        }
        scc_list.resize(num);
        rep(i, num) scc_list[i].reserve(cnt[i]);
        rep(i, n) scc_list[id[i]].eb(i);
    }
};

bool run(int v) {
	gone[cmp[v]] = 1;
	u[v] = 1;
	for (int i = 0; i < (int)g[v].size(); ++i) {
		int to = g[v][i].first;
		if (cmp[to] == cmp[v]) {
			if (!u[to]) {
				dep[to] = dep[v] + g[v][i].second;
				if (run(to)) return true;
			} else {
				if (dep[v] - dep[to] + g[v][i].second) return true;
			}
		}
	}
	return false;
}

bool cmp_dfs(int v) {
	if (u[v]) return cyc[v];
	u[v] = 1;
	for (int i = 0; i < (int)cmp_g[v].size(); ++i) if (cmp_dfs(cmp_g[v][i])) cyc[v] = 1;
	return cyc[v];
}

signed main() {
	scanf("%d%d%d", &n, &m, &q);
    vvl ed(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		a = z(a);
		int dir = z(b + a);
		g[a].push_back(std::make_pair(dir, b));
        ed[a].eb(dir);
		tr[dir].push_back(a);
	}
    SCC scc(ed);
    rep(i,n) cmp[i]=scc.id[i]+1;
	memset(u, 0, sizeof u);
	for (int i = 0; i < n; ++i) if (!gone[cmp[i]] && run(i)) cyc[cmp[i]] = 1;
	for (int i = 0; i < n; ++i) for (int j = 0; j < (int)g[i].size(); ++i) {
		int to = g[i][j].first;
		if (cmp[i] != cmp[to]) cmp_g[cmp[i]].push_back(cmp[to]);
	}
	memset(u, 0, sizeof u);
	for (int i = 1; i <= scc.num; ++i) cmp_dfs(i);
	while (q--) {
		int x;
		scanf("%d", &x);
		x = z(x);
		printf("%s\n", cyc[cmp[x]] ? "Yes" : "No");
	}
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 8360kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

No
No
Yes

result:

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