QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#810957 | #9810. Obliviate, Then Reincarnate | False0099 | WA | 0ms | 42048kb | C++20 | 3.2kb | 2024-12-12 13:56:59 | 2024-12-12 13:57:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e6 + 10, M = 2e6 + 10;
int n, m, mod;
int h[N], e[M << 1], ne[M << 1], idx, val[N]; // 原图参数
/*tarjan中间量*/
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
/*tarjan中间量*/
int id[N], scc_size[N]; // 新旧关系
int scc_cnt; // 新图的n
int hs[N], sum[N], dp[N], in[N]; // 新图的参数
int ans;
void add(int h[], int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u)
{
dfn[u] = low[u] = ++timestamp;
stk[++top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j])
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
++scc_cnt;
int y;
do
{
y = stk[top--];
in_stk[y] = false;
id[y] = scc_cnt;
sum[scc_cnt] += val[y]; // 处理我们的合并点
scc_size[scc_cnt]++;
} while (y != u);
}
}
void topsort()
{
queue<int> q;
for (int i = 1; i <= scc_cnt; i++)
{
if (in[i] == 0)
{
q.push(i);
}
}
while (!q.empty())
{
int now = q.front();
q.pop();
if (scc_size[now] > 1)
{
dp[now] = 1;
}
for (int i = hs[now]; i != -1; i = ne[i])
{
int v = e[i];
in[v]--;
dp[v] = (dp[v] | dp[now]);
if (in[v] == 0)
{
q.push(v);
}
}
}
}
signed main()
{
memset(h, -1, sizeof h);
memset(hs, -1, sizeof hs);
int q;
cin >> n >> m >> q;
// for (int i = 1; i <= n; i++)
// {
// cin >> val[i];
// }
set<array<int, 2>> edges;
while (m--)
{
int a, b;
cin >> a >> b;
a %= n;
b %= n;
a = (a + n) % n;
if (b == 0)
{
continue;
}
else
{
edges.insert({a, (a + b) % n});
// cerr << a << " " << (a + b) % n << endl;
add(h, a, (a + b) % n);
}
}
for (int i = 1; i <= n; i++)
{
if (!dfn[i])
{
tarjan(i);
}
}
for (int i = 1; i <= n; i++)
{
for (int j = h[i]; ~j; j = ne[j])
{
int k = e[j];
int a = id[i], b = id[k];
if (a != b)
{
add(hs, b, a);
in[a]++;
}
}
}
for (int i = 1; i <= n; i++)
{
if (edges.count({i, i}))
{
dp[id[i]] = 1;
}
}
topsort();
while (q--)
{
int u;
cin >> u;
if (dp[id[u]] == true)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
// cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 42048kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
No No No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'