QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#786514#9810. Obliviate, Then ReincarnateZy01WA 0ms9656kbC++141.7kb2024-11-26 21:53:332024-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:34]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 9656kb
  • [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;
}

詳細信息

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'