QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #881288 | #9810. Obliviate, Then Reincarnate | UESTC_NLNS | Compile Error | / | / | C++20 | 5.8kb | 2025-02-04 14:42:53 | 2025-02-04 14:42:54 |
Judging History
This is the latest submission verdict.
- [2025-02-04 14:42:54]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2025-02-04 14:42:53]
- Submitted
answer
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
using pii = pair<int, int>;
using ll = long long;
struct solver {
int n, m, q;
vector<int> dfn, low, stk, id;
vector<vector<pii>> g;
vector<vector<int>> ig;
vector<int> bl;
vector<int> tag;
vector<int> vis;
vector<ll> dis;
int cur = 1, cnt = 1;
solver(int n) : n(n), dis(n + 1), tag(n + 1), ig(n + 1),
dfn(n + 1), g(n + 1), bl(n + 1),
low(n + 1), stk(), id(n + 1, -1), vis(n + 1) {}
void tarjan(int u) {
dfn[u] = low[u] = ++cur;
stk.push_back(u);
for (auto [v, w] : g[u]) {
if (dfn[v] == 0)
tarjan(v), low[u] = min(low[u], low[v]);
else if (id[v] == -1)
low[u] = min(low[u], low[v]);
}
if (dfn[u] == low[u]) {
int v;
do {
v = stk.back();
id[v] = cnt;
stk.pop_back();
} while (v != u);
cnt++;
}
}
int check(int u) {
assert(id[u] != -1);
for (const auto [v, w] : g[u]) {
assert(w);
if (id[v] != id[u]) continue;
ll nd = dis[u] + w;
if (!vis[v]) {
dis[v] = nd, vis[v] = 1;
if (check(v)) return tag[u] = 1;
} else {
if (nd != dis[v]) {
return tag[v] = 1;
}
}
}
return 0;
}
void fan() {
queue<int> q;
for (int i = 0; i < n; ++i)
if (tag[i]) q.push(i);
while (q.size()) {
int u = q.front();
q.pop();
for (const auto v : ig[u]) {
if (!tag[v]) tag[v] |= 1, q.push(v);
}
}
}
int norm(ll x) {
return (x % n + n) % n;
}
void solve() {
cin >> m >> q;
for (int i = 0; i < m; ++i) {
int x, w, y;
cin >> x >> w;
y = norm(x + w),
x = norm(x);
if (x == y) {
if (w) tag[x] = 1;
} else {
g[x].push_back({y, w});
ig[y].push_back(x);
}
}
for (int i = 0; i < n; ++i) {
if (id[i] == -1) {
tarjan(i);
vis[i] = 1;
tag[i] |= check(i);
}
}
fan();
for (int i = 0; i < q; ++i) {
int u;
cin >> u;
u = norm(u);
cout << (tag[u] ? "Yes" : "No") << '\n';
}
}
};
signed main() {
cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
int n;
cin >> n;
solver s(n);
s.solve();
}
/*
3 3 3
1 1
2 -2
3 4
1
2
3
3 3 3
1 3
1 1
2 -1
1 2 3
*/#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
using pii = pair<int, int>;
using ll = long long;
struct solver {
int n, m, q;
vector<int> dfn, low, stk, id;
vector<vector<pii>> g;
vector<vector<int>> ig;
vector<int> bl;
vector<int> tag;
vector<int> vis;
vector<ll> dis;
int cur = 0, cnt = 0;
solver(int n) : n(n), dis(n + 1), tag(n + 1), ig(n + 1),
dfn(n + 1), g(n + 1), bl(n + 1),
low(n + 1), stk(), id(n + 1, -1), vis(n + 1) {}
void tarjan(int u) {
dfn[u] = low[u] = ++cur;
stk.push_back(u);
for (auto [v, w] : g[u]) {
if (dfn[v] == 0)
tarjan(v), low[u] = min(low[u], low[v]);
else if (id[v] == -1)
low[u] = min(low[u], low[v]);
}
if (dfn[u] == low[u]) {
int v;
do {
v = stk.back();
id[v] = cnt;
stk.pop_back();
} while (v != u);
cnt++;
}
}
int check(int u) {
assert(id[u] != -1);
for (const auto [v, w] : g[u]) {
if (id[v] != id[u]) continue;
ll nd = dis[u] + w;
if (!vis[v]) {
dis[v] = nd, vis[v] = 1;
if (check(v)) return 1;
} else {
if (nd != dis[v]) {
return 1;
}
}
}
return 0;
}
void fan() {
queue<int> q;
for (int i = 0; i < n; ++i)
if (tag[i]) q.push(i);
while (q.size()) {
int u = q.front();
q.pop();
for (const auto v : ig[u]) {
if (!tag[v]) tag[v] |= 1, q.push(v);
}
}
}
int norm(ll x) {
return (x % n + n) % n;
}
void solve() {
cin >> m >> q;
for (int i = 0; i < m; ++i) {
int x, w, y;
cin >> x >> w;
x = norm(x), y = norm(x + w);
if (x == y) {
if (w) tag[x] = 1;
}
g[x].push_back({y, w});
ig[y].push_back(x);
}
for (int i = 0; i < n; ++i) {
if (id[i] == -1) {
tarjan(i);
vis[i] = 1;
tag[i] |= check(i);
}
}
fan();
for (int i = 0; i < q; ++i) {
int u;
cin >> u;
u = norm(u);
cout << (tag[u] ? "Yes" : "No") << '\n';
}
}
};
signed main() {
cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
int n;
cin >> n;
solver s(n);
s.solve();
}
/*
3 3 3
1 1
2 -2
3 4
1
2
3
3 3 3
1 3
1 1
2 -1
1 2 3
*/
详细
answer.code:141:8: error: redefinition of ‘struct solver’
141 | struct solver {
| ^~~~~~
answer.code:10:8: note: previous definition of ‘struct solver’
10 | struct solver {
| ^~~~~~
answer.code:238:8: error: redefinition of ‘int main()’
238 | signed main() {
| ^~~~
answer.code:110:8: note: ‘int main()’ previously defined here
110 | signed main() {
| ^~~~