QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#800802 | #9810. Obliviate, Then Reincarnate | ucup-team5008 | WA | 3ms | 8360kb | C++23 | 3.3kb | 2024-12-06 15:46:21 | 2024-12-06 15:46:27 |
Judging History
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;
}
詳細信息
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'