QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#787313 | #9810. Obliviate, Then Reincarnate | UESTC_OldEastWest# | TL | 171ms | 29096kb | C++20 | 3.8kb | 2024-11-27 11:04:31 | 2024-11-27 11:04:32 |
Judging History
answer
#include <bits/stdc++.h>
const long long INF = 1e16;
namespace SPFA {
int n;
std::vector<int> cnt, vis, in_s;
std::vector<long long> dis;
std::vector<std::vector<std::pair<int, int> > > G;
void Init(int _n, std::vector<std::vector<std::pair<int, int> > > _G) {
n = _n, G = _G;
dis = std::vector<long long> (n, INF);
cnt = vis = in_s = std::vector<int> (n);
}
bool SPFA(std::vector<int> &s, int coef) {
if (s.empty()) return false;
// std::cout << "Begin" << std::endl;
for (int u : s) in_s[u] = 1;
int st = s[0];
dis[st] = 0, vis[st] = 1;
int head = 0, tail = 1;
std::vector<int> que(1, st);
bool neg_circle = false;
while (head < tail) {
int u = que[head++];
vis[u] = 0;
for (auto [v, w] : G[u]) {
if (!in_s[v]) continue;
w *= coef;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) {neg_circle = true; break;}
if (!vis[v]) que.emplace_back(v), ++tail, vis[v] = 1;
}
}
}
for (int u : s) dis[u] = INF, cnt[u] = vis[u] = in_s[u] = 0;
// std::cout << "End" << std::endl;
return neg_circle;
}
}
void charming() {
int n, m, q; std::cin >> n >> m >> q;
std::vector<std::vector<std::pair<int, int> > > G(n);
for (int i = 0, a, b, c; i < m; ++i) {
std::cin >> a >> b;
a = ((a % n) + n) % n;
c = (((a + b) % n) + n) % n;
G[a].emplace_back(std::make_pair(c, b));
// std::cout << "G Add Edge " << a << ' ' << c << ' ' << b << '\n';
}
int tot = 0, scc_cnt = 0;
std::vector<int> dfn(n, -1), low(n, -1), bel(n, -1), stk;
std::vector<std::vector<int> > scc;
auto Tarjan = [&](auto &&self, int u) -> void {
dfn[u]= low[u] = tot++;
stk.emplace_back(u);
for (auto [v, _] : G[u]) {
if (dfn[v] == -1) {
self(self, v);
low[u] = std::min(low[u], low[v]);
} else if (bel[v] == -1) low[u] = std::min(low[u], dfn[v]);
}
if (low[u] >= dfn[u]) {
bel[u] = scc_cnt;
std::vector<int> new_scc;
while (stk.back() != u) {
bel[stk.back()] = scc_cnt;
new_scc.emplace_back(stk.back());
stk.pop_back();
}
new_scc.emplace_back(u);
stk.pop_back();
scc.emplace_back(new_scc);
++scc_cnt;
}
};
for (int u = 0; u < n; ++u) if (dfn[u] == -1) Tarjan(Tarjan, u);
// for (int i = 0; i < n; ++i) std::cout << bel[i] << ' ';
// std::cout << '\n';
// std::cout << 0 << std::endl;
std::vector<int> du(scc_cnt);
std::vector<std::vector<int> > nG(scc_cnt);
for (int u = 0; u < n; ++u) {
for (auto [v, _] : G[u]) {
if (bel[u] != bel[v]) {
// std::cout << "nG Add edge " << ' ' << bel[v] << ' ' << bel[u] << std::endl;
nG[bel[v]].emplace_back(bel[u]);
++du[bel[u]];
}
}
}
SPFA::Init(n, G);
auto Check = [&](int id) -> bool {
// std::cout << id << ' ' << SPFA::SPFA(scc[id], 1) << ' ' << SPFA::SPFA(scc[id], -1) << '\n';
return SPFA::SPFA(scc[id], 1) | SPFA::SPFA(scc[id], -1);
};
// std::cout << 1 << std::endl;
int head = 0, tail = 0;
std::vector<int> que, f(n);
for (int u = 0; u < scc_cnt; ++u) if (!du[u]) que.emplace_back(u), ++tail;
while (head < tail) {
int u = que[head++];
if (!f[u]) f[u] |= Check(u);
for (int v : nG[u]) {
--du[v];
f[v] |= f[u];
if (!du[v]) que.emplace_back(v), ++tail;
}
}
// std::cout << 2 << std::endl;
for (int i = 0, x; i < q; ++i) {
std::cin >> x;
x = ((x % n) + n) % n;
x = bel[x];
if (f[x]) std::cout << "Yes\n";
else std::cout << "No\n";
}
}
signed main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
charming();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
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: 3556kb
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: 3548kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: 0
Accepted
time: 171ms
memory: 29096kb
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:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 500000 tokens
Test #6:
score: -100
Time Limit Exceeded
input:
100848 500000 500000 720352587 361776806 231853504 -933882325 960971230 -83519300 -152772415 -631132247 842871215 -666621297 857194330 -754943024 -698506963 -705416545 -3551931 -927937446 628710320 -942247987 674921043 847145884 -325629529 475694308 -339363446 686789318 236702996 654762989 420412365...