QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#804585 | #9810. Obliviate, Then Reincarnate | chzhc_ | TL | 0ms | 32252kb | C++14 | 3.9kb | 2024-12-08 00:38:31 | 2024-12-08 00:38:32 |
Judging History
answer
#include <bits/stdc++.h>
template < typename T >
inline void read(T &cnt)
{
cnt = 0; char ch = getchar(); bool op = 1;
for (; ! isdigit(ch); ch = getchar())
if (ch == '-') op = 0;
for (; isdigit(ch); ch = getchar())
cnt = cnt * 10 + ch - 48;
cnt = op ? cnt : - cnt;
}
const int N = 5e5 + 10;
const int M = 5e5 + 10;
namespace E1
{
int head[N], nxt[M], to[M], val[M], tot;
inline void add(int u, int v, int w)
{
// std::cout << "edge " << u << ' ' << v << '\n';
nxt[++ tot] = head[u];
head[u] = tot;
to[tot] = v;
val[tot] = w;
}
}
namespace E2
{
int head[N], nxt[M], to[M], tot;
inline void add(int u, int v)
{
// std::cout << "EDGE " << u << ' ' << v << '\n';
nxt[++ tot] = head[u];
head[u] = tot;
to[tot] = v;
}
}
int n, m, q, valteam[N], in[N];
int dfn[N], low[N], dt;
int col[N], ct;
int sck[N], st;
std::vector < int > set[N];
bool choose[N];
inline void tarjan(int u)
{
++ dt; dfn[u] = low[u] = dt;
++ st; sck[st] = u;
for (int i = E1::head[u]; i; i = E1::nxt[i])
{
int v = E1::to[i];
if (! dfn[v])
{
tarjan(v);
low[u] = std::min(low[u], low[v]);
}
else low[u] = std::min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
++ ct;
while (sck[st] != u)
{
valteam[ct] ++; col[sck[st]] = ct; set[ct].push_back(sck[st]); st --;
}
valteam[ct] ++; col[sck[st]] = ct; set[ct].push_back(sck[st]); st --;
}
}
std::queue < int > Q;
int opt[N], flg[N], vis[N], h[N], nowcase = 0;
inline void dfs(int x) {
vis[x] = 1;
for (int i = E1::head[x]; i; i = E1::nxt[i]) {
int v = E1::to[i];
if (choose[v] == 0) continue;
if (vis[v] == 0) h[v] = h[x] + E1::val[i];
else if (h[v] != h[x] + E1::val[i]) {
nowcase = 1;
return;
}
if (vis[v] == 0) dfs(v);
}
}
inline bool check(int color) {
nowcase = 0;
int beg = -1;
for (auto it : set[color])
choose[it] = 1, beg = it;
h[beg] = 1;
dfs(beg);
for (auto it : set[color])
choose[it] = 0, vis[it] = 0;
if (nowcase == 1) return 1;
else return 0;
}
int main()
{
read(n), read(m), read(q);
for (int i = 1; i <= m; ++ i)
{
int u, v, b; read(u), read(v); b = v;
if (v == 0) continue;
u = (((u % n) + n) % n);
v = (((u + v) % n) + n) % n + 1;
u ++;
if (u != v)
E1::add(u, v, b);
else opt[u] = 1;
}
for (int i = 1; i <= n; ++ i)
if (! dfn[i]) tarjan(i);
for (int i = 1; i <= n; ++ i) {
// std::cout << "col " << i << ' ' << col[i] << '\n';
int color = col[i];
if (opt[i] == 1 || (valteam[color] > 1 && check(color))) {
flg[color] = 1;
}
}
for (int u = 1; u <= n; ++ u)
{
for (int i = E1::head[u]; i; i = E1::nxt[i])
{
int v = E1::to[i];
if (col[u] != col[v])
{
E2::add(col[v], col[u]);
in[col[u]] ++;
}
}
}
for (int i = 1; i <= ct; ++ i)
if (in[i] == 0)
Q.push(i);
while (Q.size())
{
int u = Q.front(); Q.pop();
for (int i = E2::head[u]; i; i = E2::nxt[i])
{
int v = E2::to[i];
flg[v] = std::max(flg[v], flg[u]);
in[v] --;
if (in[v] == 0) Q.push(v);
}
}
while (q --) {
int x; read(x);
x = (((x % n) + n) % n) + 1;
if (flg[col[x]] == 0) std::cout << "No\n";
else std::cout << "Yes\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32252kb
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: 30128kb
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: 26056kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 28396kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: -100
Time Limit Exceeded
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...