QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#786569 | #9810. Obliviate, Then Reincarnate | Zy01 | TL | 1ms | 9740kb | C++14 | 1.8kb | 2024-11-26 22:04:41 | 2024-11-26 22:04:41 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-26 22:04:41]
- 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;
if(ans[v]) continue;
int disv = dis[v];
dis[v] = dis[u] + w, v2[v]++;
dfs(v);
if(ans[v]) ans[u] = 1;
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7616kb
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: 9740kb
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: 9568kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7672kb
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...