QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#801023 | #9810. Obliviate, Then Reincarnate | ucup-team135# | Compile Error | / | / | Python3 | 3.6kb | 2024-12-06 17:43:58 | 2024-12-06 17:44:05 |
Judging History
This is the latest submission verdict.
- [2024-12-06 17:44:05]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-12-06 17:43:58]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
mt19937 rnd;
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do {cout<< #v <<" : {"; for(int izxc=0;izxc<v.size();++izxc) {cout << v[izxc];if(izxc+1!=v.size()) cout << ","; }cout <<"}"<< endl;} while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#define lob(a,x) lower_bound(all(a),x)
#define upb(a,x) upper_bound(all(a),x)
vector<int> find_scc(vector<vector<int>> g, int &color) {
vector<vector<int>> r(g.size());
for (int i = 0; i < g.size(); ++i) {
for (int j : g[i]) r[j].push_back(i);
}
vector<int> used(g.size()), tout(g.size());
int time = 0;
auto dfs = [&](auto dfs, int cur) -> void {
if (used[cur]) return;
used[cur] = 1;
for (int nxt : g[cur]) {
dfs(dfs, nxt);
}
tout[cur] = time++;
};
for (int i = 0; i < g.size(); ++i) if (!used[i]) dfs(dfs, i);
vector<int> ind(g.size());
iota(ind.begin(), ind.end(), 0);
sort(all(ind), [&](int i, int j){return tout[i] > tout[j];});
vector<int> scc(g.size(), -1);
auto go = [&](auto go, int cur, int color) -> void {
if (scc[cur] != -1) return;
scc[cur] = color;
for (int nxt : r[cur]) {
go(go, nxt, color);
}
};
for (int i : ind) {
if (scc[i] == -1) go(go, i, color++);
}
return scc;
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector <array <int, 3> > e;
vector <vector <int> > og(n), ng;
vector <vector <pair <int, int> > >gg(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b;
a = (a % n + n) % n;
int to = ((a + b) % n + n) % n;
og[a].app(to);
gg[a].app({to, b});
e.app({a, to, b});
}
int color = 0;
auto scc = find_scc(og, color);
ng.resize(color);
for (auto [u, v, d] : e) {
u = scc[u]; v = scc[v];
ng[u].app(v);
}
vector <int> start(color);
for (int i = 0; i < n; ++i) {
start[scc[i]]=i;
}
vector <int> p(n), used(n);
function <void(int)> dfs = [&] (int u) {
used[u] = 1;
for (auto [v, d] : gg[u]) {
if (scc[u] != scc[v]) {
continue;
}
if (!used[v]) {
p[v] = p[u] + d;
dfs(v);
}
}
};
debug("here");
for (int c = 0; c < color; ++c) {
dfs(start[c]);
}
debug("dfs");
vector <int> mon(color);
for (auto [u, v, d] : e) {
if (scc[u] == scc[v]) {
if (p[u] + d != p[v]) {
mon[scc[u]] = 1;
}
}
}
function <void(int)> go = [&] (int u) {
used[u] = 1;
for (int v : ng[u]) {
if (!used[v]) {
go(v);
mon[u] |= mon[v];
}
}
};
used.assign(color, 0);
for (int i = 0; i < color; ++i) {
if (!used[i]) {
go(i);
}
}
while (q--) {
int a; cin >> a;
a = (a % n + n) % n;
if (mon[scc[a]]) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
return 0;
}
详细
File "answer.code", line 6 int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}} ^ SyntaxError: invalid decimal literal