QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#819876 | #9810. Obliviate, Then Reincarnate | Magical_Kingdom | WA | 5ms | 44160kb | C++20 | 3.7kb | 2024-12-18 17:56:00 | 2024-12-18 17:56:02 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int maxn = 5e5 + 7;
ll n, m, q;
struct Edge {
ll v, w;
Edge(ll _v = 0, ll _w = 0)
: v(_v), w(_w) {}
};
vector<Edge> to[maxn];
ll dfn[maxn], low[maxn], cnt, tot;
ll vis[maxn], belong[maxn], inde, belong_num[maxn], num_inde;
ll indegree[maxn], outdegree[maxn];
stack<ll> st;
void tarjin(ll x) {
dfn[x] = low[x] = ++tot;
vis[x] = 1;
st.push(x);
for (auto [v, w] : to[x]) {
if (!dfn[v]) {
tarjin(v);
low[x] = min(low[x], low[v]);
} else if (vis[v] == 1) {
low[x] = min(low[x], dfn[v]);
}
}
if (dfn[x] == low[x]) {
ll v;
inde = inde + 1;
do {
v = st.top();
st.pop();
belong[v] = inde;
belong_num[inde]++;
vis[v] = 0;
} while (v != x);
}
}
ll stk[maxn], top, loc[maxn];
ll sum_min[maxn], sum_max[maxn];
bool in_stk[maxn];
set<int> visited;
bool can[maxn];
void dfs(int u) {
stk[++top] = u;
loc[u] = top;
map<ll, pll> mp;
for (auto [v, w] : to[u]) {
if (belong[v] != belong[u]) {
continue;
}
if (mp.find(v) == mp.end()) {
mp[v].first = mp[v].second = w;
} else {
mp[v].first = min(w, mp[v].first);
mp[v].second = max(w, mp[v].second);
}
}
for (auto [v, w] : mp) {
ll wmin = w.first, wmax = w.second;
if (in_stk[v] == true) {
if (sum_max[top] - sum_max[loc[v]] + wmax == 0 &&
sum_min[top] - sum_min[loc[v]] + wmin == 0) {
continue;
} else {
can[belong[u]] = true;
loc[u] = 0;
stk[top--] = 0;
return;
}
}
if (visited.find(v) != visited.end()) {
continue;
}
visited.insert(v);
in_stk[v] = true;
sum_min[top + 1] = sum_min[top] + wmin;
sum_max[top + 1] = sum_max[top] + wmax;
dfs(v);
sum_min[top + 1] = 0;
sum_max[top + 1] = 0;
in_stk[v] = false;
if (can[belong[u]] == true) {
loc[u] = 0;
stk[top--] = 0;
return;
}
}
loc[u] = 0;
stk[top--] = 0;
return;
}
set<int> nto[maxn];
void dfs2(int u) {
can[u] = true;
for (auto v : nto[u]) {
if (!can[v]) {
dfs2(v);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
ll u, w;
cin >> u >> w;
ll v = u + w;
u = (u % n + n) % n;
v = (v % n + n) % n;
to[u].push_back(Edge(v, w));
}
for (int i = 0; i < n; i++) {
if (!dfn[i]) {
tarjin(i);
}
}
for (int i = 1; i <= inde; i++) {
visited.clear();
top = 0;
sum_min[i] = sum_max[i] = 0;
in_stk[i] = 1;
dfs(i);
in_stk[i] = 0;
}
for (int u = 0; u < n; u++) {
for (auto e : to[u]) {
int v = e.v;
if (belong[u] != belong[v]) {
nto[belong[v]].insert(belong[u]);
}
}
}
for (int i = 1; i <= inde; i++) {
if (can[i] == true) {
dfs2(i);
}
}
while (q--) {
ll x;
cin >> x;
x = (x % n + n) % n;
if (can[belong[x]]) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 42920kb
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: 42940kb
input:
3 2 3 1 1 -1 0 1 2 3
output:
No No No
result:
ok 3 tokens
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 44160kb
input:
1 1 1 0 1000000000 -1000000000
output:
No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'