QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#819866 | #9810. Obliviate, Then Reincarnate | ljljljlj | WA | 6ms | 17760kb | C++20 | 2.3kb | 2024-12-18 17:51:08 | 2024-12-18 17:51:08 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
vector<pii> tu[1001000];
vector<int> tu1[1001000];
const int N = 1e6 + 10;
int low[N], dfn[N], vis[N], be[N], ok[N], sum[N];
int total, cnt, inde;
stack<int> st;
int flag;
void tarjan(int x) {
dfn[x] = low[x] = ++total;
vis[x] = 1;
st.push(x);
for (auto e : tu[x]) {
if (!dfn[e.first]) {
tarjan(e.first);
low[x] = min(low[e.first], low[x]);
} else if (vis[e.first] == 1) {
low[x] = min(low[x], dfn[e.first]);
}
}
if (dfn[x] == low[x]) {
int v;
inde = inde + 1;
do {
v = st.top();
st.pop();
be[v] = inde;
vis[v] = 0;
} while (v != x);
}
}
void dfs(int u) {
vis[u] = 1;
for (auto [v, w] : tu[u]) {
if (be[v] != be[u])
continue;
if (vis[v]) {
if (sum[v] != sum[u] + w)
ok[v] = 1;
} else {
sum[v] = sum[u] + w;
dfs(v);
}
}
}
void dfs1(int u) {
vis[u] = 1;
for (int x : tu1[u])
if (!vis[x])
dfs1(x);
ok[u] = 1;
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
int temp = (x % n + n) % n;
int temp2 = ((x + y) % n + n) % n;
int val = y;
tu[temp].push_back({temp2, val});
tu1[temp2].push_back(temp);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i])
tarjan(i);
}
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
dfs(i);
}
}
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++) {
if (!vis[i] && ok[i]) {
dfs1(i);
}
}
while (q--) {
int temp;
cin >> temp;
temp = ((temp % n) + n) % n;
cout << (ok[temp] == 1 ? "Yes\n" : "No\n");
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
// while (1)
// ;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 17760kb
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: 6ms
memory: 16808kb
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: 0ms
memory: 16560kb
input:
1 1 1 0 1000000000 -1000000000
output:
No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'