QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#790764#9810. Obliviate, Then ReincarnateSSAABBEERRTL 200ms31776kbC++202.3kb2024-11-28 15:15:102024-11-28 15:15:11

Judging History

This is the latest submission verdict.

  • [2024-11-28 15:15:11]
  • Judged
  • Verdict: TL
  • Time: 200ms
  • Memory: 31776kb
  • [2024-11-28 15:15:10]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, a, b) for(int i = a; i <= b; i ++ )
#define pre(i, a, b) for(int i = a; i >= b; i -- )
const int N = 1e6 + 10, M = 1e6 + 10;
int stk[M], e[N], w[N], ne[N], h[M], hs[M], idx, top, cnt, id[M], n, m, p, dfn[M], low[M], times, f[M], g[M], sz[M], dep[N];
bool in_stk[M], ff[N];
int qq, stt[N];
void add(int a, int b, int ww)
{
    w[idx] = ww, e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
    dfn[u] = low[u] = ++ times;
    stk[++top] = u, in_stk[u] = true;
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            dep[j] = dep[u] + w[i];
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(in_stk[j])
        {
            if(dep[j] != dep[u] + w[i])
            {
                ff[j] = 1;
            }
            low[u] = min(low[u], dfn[j]);
        }
    }
    if(dfn[u] == low[u])
    {
        cnt ++ ;
        int y;
        do
        {
            y = stk[top -- ];
            id[y] = cnt;
            sz[cnt] ++ ;
            in_stk[y] = false;
        }while(y != u);
    }
}
vector<int>pp[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    memset(h, -1, sizeof h);
    cin >> n >> m >> qq;
    rep(i, 1, m)
    {
        int a, b;
        cin >> a >> b;
        int u = (a % n + n) % n;
        int v = ((a + b) % n + n) % n;
        // cout<<u<<" "<<v<<endl;
        add(u, v, b);
    }
    rep(i, 0, n - 1) if(!dfn[i]) tarjan(i);
    queue<int>q;
    rep(i, 0, n - 1)
    {
        if(ff[i]) q.push(id[i]);
    }
    rep(u, 0, n - 1)
    {
        for(int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            pp[id[j]].push_back(id[u]);
        }
    }
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for(auto j : pp[u])
        {
            if(ff[j]) continue;
            ff[j] = 1;
            q.push(j);
        }
    }
    while(qq -- )
    {
        int x;
        cin >> x;
        x = (x % n + n) % n;
        if(ff[id[x]]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 19996kb

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: 20192kb

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: 20020kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 0ms
memory: 19948kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: 0
Accepted
time: 200ms
memory: 31776kb

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:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 500000 tokens

Test #6:

score: -100
Time Limit Exceeded

input:

100848 500000 500000
720352587 361776806
231853504 -933882325
960971230 -83519300
-152772415 -631132247
842871215 -666621297
857194330 -754943024
-698506963 -705416545
-3551931 -927937446
628710320 -942247987
674921043 847145884
-325629529 475694308
-339363446 686789318
236702996 654762989
420412365...

output:


result: