QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789493 | #9810. Obliviate, Then Reincarnate | xhytom | TL | 1ms | 3788kb | C++23 | 3.4kb | 2024-11-27 20:33:29 | 2024-11-27 20:33:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, m, q;
std::cin >> n >> m >> q;
std::vector<std::pair<int, int>> edges(m);
vector<vector<pair<int,int>>> adj(n);
vector<vector<pair<int,int>>> bac(n);
std::map<std::pair<int, int>, int> is;
std::vector<int> cnt(n + 1);
for (auto &[a, b] : edges) {
cin >> a >> b;
a = (a % n + n) % n;
int u = a, v = u + b;
int w = 0;
w = v / n;
v -= v / n * n;
while (v < 0) {
v += n;
w -= 1;
}
while (v >= n) {
v -= n;
w += 1;
}
std::cerr << "?" << u << " " << v << " " << w << std::endl;
if (!is.count({u, v})) {
is[{u, v}] = w;
} else if(is[{u, v}] != w) {
is[{u, v}] = 1E18;
}
bac[v].push_back({u, w});
}
for (auto [tmp, w] : is) {
auto [u, v] = tmp;
if (w == 1E18) {
adj[u].push_back({v, 1E18});
} else {
adj[u].push_back({v, w});
}
}
std::vector<int> vis(n, -1E18), cur(n, -1E18);
std::vector<int> ok(n, 0);
for (int i = 0; i < n; i++) {
if (vis[i] == -1E18) {
auto dfs = [&](auto self, int x, int fx, int d, int all) -> void {
vis[x] = 1;
cur[x] = d;
cnt[x] = all;
// std::cerr << "DFS" << x << " " << fx << " " << d << std::endl;
for (auto [y, w] : adj[x]) {
if (vis[y] == -1E18) {
if (w == 1E18) {
self(self, y, x, 1E18, all + 1);
} else {
self(self, y, x, d + w, all);
}
} else {
std::cerr << "!!!" << x << " " << y << " " << cur[x] << " " << cur[y] << " " << d << " " << w << std::endl;;
if ((cur[y] != -1E18 && (cur[y] != d + w || w == 1E18)) || (cnt[x] - cnt[y])) {
std::cerr << "TRUE" << std::endl;
ok[y] = true;
}
}
ok[x] |= ok[y];
}
cur[x] = -1E18;
};
dfs(dfs, i, -1, 0, 0);
}
std::cerr << "####" << std::endl;
for (int i = 0; i < n; i++) {
std::cerr << vis[i] << " \n"[i == n - 1];
}
for (int i = 0; i < n; i++) {
std::cerr << ok[i] << " \n"[i == n - 1];
}
}
std::queue<int> que;
for (int i = 0; i < n; i++) {
if (ok[i]) {
que.push(i);
}
}
while (!que.empty()) {
int x = que.front();
que.pop();
for (auto [y, w] : bac[x]) {
if (!ok[y]) {
ok[y] = true;
que.push(y);
}
}
}
for (int i = 1; i <= q; i++) {
int x;
std::cin >> x;
x = (x % n + n) % n;
std::cout << (ok[x] ? "Yes" : "No") << "\n";
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t = 1;
// std::cin >> t;
while (t --) {
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3788kb
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: 1ms
memory: 3528kb
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: 3544kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3624kb
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...