QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#780888 | #9810. Obliviate, Then Reincarnate | hhhyh | TL | 0ms | 3872kb | C++23 | 2.2kb | 2024-11-25 13:51:30 | 2024-11-25 13:51:31 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-25 13:51:30]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(x) x.begin(), x.end()
#define int long long
void solve()
{
int n, m, q;
cin >> n >> m >> q;
vector<int> f(n), ok(n, 1);
iota(all(f), 0ll);
auto find = [&](auto find, int x) -> int
{
return f[x] == x ? f[x] : f[x] = find(find, f[x]);
};
vector<int> in(n), out(n);
vector<vector<pair<int, int>>> e(n);
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
int w = b;
a = (a % n + n) % n;
if (b == 0)
continue;
b = (b % n + n) % n;
b = (b + a) % n;
e[a].push_back({b, w});
g[b].push_back({a, w});
in[b]++;
out[a]++;
}
{
queue<int> q;
vector<i64> dep(n);
vector<int> vis(n);
function<void(int)> tarjan = [&](int x)
{
vis[x] = 1;
for (auto [y, w] : e[x])
{
if (vis[y])
{
if (w + dep[x] - dep[y] != 0)
q.push(x);
}
else
{
dep[y] = dep[x] + w;
tarjan(y);
}
}
vis[x] = 0;
};
for (int i = 0; i < n; i++)
if (!vis[i])
tarjan(i);
ok.assign(n, 0);
while (!q.empty())
{
int x = q.front();
q.pop();
if (ok[x] != 0)
continue;
ok[x] = 1;
for (auto [y, w] : g[x])
{
if (ok[y])
continue;
ok[y] = 1;
q.push(y);
}
}
}
for (int i = 0; i < q; i++)
{
int x;
cin >> x;
x = (x % n + n) % n;
if (ok[x])
cout << "Yes\n";
else
cout << "No\n";
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
while (T--)
solve();
}
/*
3 2 3
1 1
-1 0
1
2
3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3872kb
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: 3828kb
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: 3632kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
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...