QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#786569#9810. Obliviate, Then ReincarnateZy01TL 1ms9740kbC++141.8kb2024-11-26 22:04:412024-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]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 9740kb
  • [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...

output:


result: