QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811024 | #9810. Obliviate, Then Reincarnate | False0099 | WA | 590ms | 83512kb | C++20 | 3.2kb | 2024-12-12 14:48:43 | 2024-12-12 14:48:45 |
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;
bool vis[N];
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]++;
// dp[scc_cnt] |= vis[y];
} while (y != u);
}
}
void topsort()
{
queue<int> q;
for (int i = 1; i <= scc_cnt; i++)
{
if (in[i] == 0)
{
//cerr << i << endl;
q.push(i);
if (sum[i] != 0)
{
dp[i] = 1;
}
}
}
while (!q.empty())
{
int now = q.front();
q.pop();
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;
// set<array<int, 2>> edges;
vector<array<int, 3>> edge;
while (m--)
{
int a, b;
cin >> a >> b;
a %= n;
// b %= n;
a = (a + n) % n;
edge.push_back({a, (a + b + n) % n, b});
add(h, a, (a + b + n) % n);
}
for (int i = 0; i < n; i++)
{
if (!dfn[i])
{
tarjan(i);
}
}
for (int i = 0; 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 (auto [u, v, w] : edge)
{
if (id[u] == id[v])
{
sum[id[u]] += w;
}
}
topsort();
// cerr << "q" << endl;
while (q--)
{
int u;
cin >> u;
u %= n;
u = (u + n) % n;
//cerr << u << " " << id[u] << endl;
if (dp[id[u]] == true)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
// cout << ans << endl;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 49804kb
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: 5ms
memory: 47596kb
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: 46212kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 46680kb
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: 583ms
memory: 83512kb
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: 590ms
memory: 78508kb
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'