QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#788417 | #9810. Obliviate, Then Reincarnate | LGyxj | WA | 231ms | 56868kb | C++14 | 2.6kb | 2024-11-27 16:51:37 | 2024-11-27 16:51:37 |
Judging History
answer
//////////////////////////
// Author: lnyxj
// Time: 2024-11-27 16:20:18
///////////////////////////
#include <bits/stdc++.h>
#define xx first
#define yy second
// #define int long long
// #define double long double
using namespace std;
const int N = 5e5 + 5, mod = 998244353, inv2 = mod + 1 >> 1, inf = 0x3f3f3f3f;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef long long ll;
int n, m, qs;
int a[N];
int num, h[N], to[N], w[N], nxt[N];
inline void adde(int x, int y, int z) { ++ num; nxt[num] = h[x]; w[num] = z; to[num] = y; h[x] = num; }
stack<int> stk;
int low[N], pre[N], dfn;
int col[N], cnt;
bool tst[N];
bool solvec(const vector<int>& pts) {
static vector<pii> edgs[N];
static bool vis[N];
static int dis[N];
for (int v : pts) {
dis[v] = -1; vis[v] = 0;
for (int i = h[v]; i; i = nxt[i])
if (col[to[i]] == col[v]) edgs[v].push_back({to[i], w[i]});
}
priority_queue<pii, vector<pii>, greater<pii> > q;
q.push({pts[0], dis[pts[0]] = 0});
while (!q.empty()) {
const auto [x, d] = q.top(); q.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto [y, w] : edgs[x]) {
if (dis[y] == -1) dis[y] = d + w;
else if (dis[y] != d + w) return 1;
}
}
return 0;
}
void tarjan(int x) {
stk.push(x);
low[x] = pre[x] = ++ dfn;
for (int i = h[x]; i; i = nxt[i]) {
const int y = to[i];
if (!pre[y]) {
tarjan(y);
low[x] = min(low[x], low[y]);
} else low[x] = min(low[x], pre[y]);
}
if (low[x] >= pre[x]) {
int p = -1; ++ cnt;
vector<int> cur;
while (p != x) {
p = stk.top(); stk.pop();
col[p] = cnt;
cur.push_back(p);
}
tst[cnt] = solvec(cur);
}
}
void solve() {
cin >> n >> m >> qs;
for (int i = 1, x, y; i <= m; ++ i) {
cin >> x >> y;
adde(((x % n) + n) % n, ((x + y) % n + n) % n, y);
}
for (int i = 0; i < n; ++ i)
if (!pre[i]) tarjan(i);
static vector<int> edgx[N];
static int d[N];
for (int i = 0; i < n; ++ i) {
for (int j = h[i]; j; j = nxt[j]) {
const int p = to[j];
if (col[i] != col[p]) {
edgx[col[p]].push_back(col[i]);
++ d[col[i]];
}
}
}
queue<int> q;
for (int i = 1; i <= cnt; ++ i)
if (!d[i]) q.push(i);
while (!q.empty()) {
const int x = q.front(); q.pop();
for (int y : edgx[x]) {
-- d[y];
tst[y] |= tst[x];
if (!d[y])
q.push(y);
}
}
for (int i = 1, x; i <= qs; ++ i)
cin >> x, cout << "No\n\0Yes\n" + (tst[col[(x % n + n) % n]]) * 4;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
while (T --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 38312kb
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: 36388kb
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: 6ms
memory: 36220kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 3ms
memory: 39024kb
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: 197ms
memory: 52056kb
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
Wrong Answer
time: 231ms
memory: 56868kb
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...
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:
wrong answer 1st words differ - expected: 'Yes', found: 'No'