QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786514 | #9810. Obliviate, Then Reincarnate | Zy01 | WA | 0ms | 9656kb | C++14 | 1.7kb | 2024-11-26 21:53:33 | 2024-11-26 21:53:34 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-26 21:53:33]
- Submitted
answer
#include<cstdio>
using namespace std;
const int N = 5e5 + 10;
int n, m, q, v1[N], v2[N], v3[N], ans[N], dis[N];
int tot = 0, head[N], pre[N], ver[N], edge[N];
void add(int u, int v, int w) {
ver[++tot] = v, edge[tot] = w, pre[tot] = head[u], head[u] = tot;
}
int tot2 = 0, head2[N], pre2[N], ver2[N];
void add2(int u, int v) {
ver2[++tot2] = v, pre2[tot2] = head2[u], head2[u] = tot2;
}
int sol(int x) {
if(x < 0) {
int t = x / n;
x += (t + 2) * n;
}
x %= n;
return x;
}
void dfs(int u) {
//printf("u %d\n", u);
v1[u] = 1;
if(v2[u] > 1) return;
for(int i = head[u]; i; i = pre[i]) {
int v = ver[i], w = edge[i];
if(v2[v] > 0 && dis[v] != dis[u] + w) ans[v] = 1;
int disv = dis[v];
dis[v] = dis[u] + w, v2[v]++;
if(v2[v] > 1) dfs(v);
dis[v] = disv, v2[v]--;
}
}
void dfs2(int u) {
if(v3[u]) return;
v3[u]++;
for(int i = head2[u]; i; i = pre2[i]) {
int v = ver2[i];
if(ans[u]) ans[v] = 1;
dfs2(v);
}
}
int main() {
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
a = sol(a);
int t = sol(a + b);
//printf("%d %d %d\n", a, t, b);
add(a, t, b);
add2(t, a);
}
for(int i = 0; i < n; i++) {
if(v1[i] == 0) dfs(i);
}
for(int i = 0; i < n; i++) {
if(v3[i] == 0) dfs2(i);
}
// for(int i = 0; i < n; i++) {
// printf("%d\n", ans[i]);
// }
while(q--) {
int x;
scanf("%d", &x);
x = sol(x);
if(ans[x]) puts("Yes");
else puts("No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9656kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
No No No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'