QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#804555 | #9810. Obliviate, Then Reincarnate | chzhc_ | ML | 3ms | 32228kb | C++14 | 3.8kb | 2024-12-08 00:02:07 | 2024-12-08 00:02:07 |
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[N], 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;
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;
if (u != v)
E1::add(u, v, b);
else opt[u] = 1;
}
for (int i = 0; i < n; ++ i)
if (! dfn[i]) tarjan(i);
for (int i = 0; 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);
if (flg[col[x]] == 0) std::cout << "No\n";
else std::cout << "Yes\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 32228kb
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: 30240kb
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: 3ms
memory: 26152kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Memory Limit Exceeded
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000