QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783394 | #9810. Obliviate, Then Reincarnate | cdd | RE | 0ms | 3820kb | C++23 | 3.9kb | 2024-11-26 09:33:00 | 2024-11-26 09:33:01 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-26 09:33:00]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef long long LL;
typedef unsigned long long uLL;
const int inf32 = 1e9;
const LL inf64 = 1e18;
struct SCC {
int n;
vector<vector<int>> G;
vector<int> dfn, low, ins, stk;
vector<int> col, siz;
int id, colcnt;
SCC() {}
SCC(int x) {
init(x);
}
void init(int x) {
n = x;
G.assign(n + 5, {});
}
void add_edge(int x, int y) {
G[x].push_back(y);
}
void dfs(int cur) {
dfn[cur] = low[cur] = ++id;
stk.push_back(cur), ins[cur] = 1;
for (auto v : G[cur]) {
if (!dfn[v]) {
dfs(v);
low[cur] = min(low[cur], low[v]);
} else if (ins[v]) {
low[cur] = min(low[cur], dfn[v]);
}
}
if (dfn[cur] == low[cur]) {
++colcnt;
int x = stk.back();
while (x != cur) {
col[x] = colcnt;
ins[x] = 0;
++siz[colcnt];
stk.pop_back();
x = stk.back();
}
col[cur] = colcnt;
ins[cur] = 0;
++siz[colcnt];
stk.pop_back();
}
}
void gets() {
dfn.assign(n + 5, 0);
low.assign(n + 5, 0);
ins.assign(n + 5, 0);
col.assign(n + 5, 0);
siz.assign(n + 5, 0);
stk.clear();
id = colcnt = 0;
for (int i = 0; i < n; i++)
if (!dfn[i]) dfs(i);
}
int diff(int x, int y) {
return col[x] != col[y];
}
};
signed main()
{
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(0);
int T = 1;
// cin >> T;
while (T--) {
int n, k, Q;
cin >> n >> k >> Q;
SCC TG(n);
vector<vector<pii>> G(n + 5);
vector<pii> e;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
int u = (x % n + n) % n, v = (u + y) % n, w = y;
// cerr << u << ' ' << v << ' ' << w << endl;
G[u].push_back({v, w});
TG.add_edge(u, v);
e.push_back({u, v});
}
TG.gets();
int len = TG.colcnt;
vector<int> vis(len + 5, 0), ff(len + 5, 0), val(n + 5, inf64);
function<int(int, int, int, int)> dfs = [&] (int cur, int ftr, int now, int s) -> int {
// cerr << cur << ' ' << s << ' ' << val[cur] << endl;
if (val[cur] != inf64) {
return s != val[cur];
}
val[cur] = s;
for (auto [v, w] : G[cur]) {
if (TG.col[v] != now) continue;
if (dfs(v, cur, now, s + w)) return 1;
}
return 0;
};
for (int i = 0; i < n; i++) {
int col = TG.col[i];
if (vis[col]) continue;
vis[col] = 1;
ff[col] = dfs(i, 0, col, 0);
}
vector<pii> l;
for (auto [u, v] : e) {
if (TG.col[u] == TG.col[v]) continue;
l.push_back({u, v});
}
sort(l.begin(), l.end(), [&](pii x, pii y) {
if (x.first != y.first) return x.first > y.first;
return x.second > y.second;
});
for (auto [u, v] : l) {
u = TG.col[u], v = TG.col[v];
// cerr << u <<' ' << v << endl;
ff[u] = max(ff[u], ff[v]);
}
// for (int i = 0; i < n; i++) cerr << TG.col[i] << ' '; cerr << endl;
// for (int i = 1; i <= len; i++) cerr << ff[i] << ' '; cerr << endl;
while (Q--) {
int x;
cin >> x;
x = (x % n + n) % n;
cout << (ff[TG.col[x]] ? "Yes\n" : "No\n");
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
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: 3488kb
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: 3556kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: -100
Runtime Error
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...