QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#804562#9810. Obliviate, Then Reincarnatechzhc_TL 3ms32448kbC++143.8kb2024-12-08 00:07:512024-12-08 00:07:52

Judging History

This is the latest submission verdict.

  • [2024-12-08 00:07:52]
  • Judged
  • Verdict: TL
  • Time: 3ms
  • Memory: 32448kb
  • [2024-12-08 00:07:51]
  • Submitted

answer

#include <bits/stdc++.h>

template < typename T > 
inline void read(T &cnt)
{
    cnt = 0; char ch = getchar(); bool op = 1;
    for (; ! isdigit(ch); ch = getchar())
        if (ch == '-') op = 0;
    for (; isdigit(ch); ch = getchar())
        cnt = cnt * 10 + ch - 48;
    cnt = op ? cnt : - cnt;
}

const int N = 5e5 + 10;
const int M = 5e5 + 10;

namespace E1
{
    int head[N], nxt[M], to[M], val[N], tot;
    inline void add(int u, int v, int w)
    {
        // std::cout << "edge " << u << ' ' << v << '\n';
        nxt[++ tot] = head[u];
        head[u] = tot;
        to[tot] = v; 
        val[tot] = w;
    }
}

namespace E2
{
    int head[N], nxt[M], to[M], tot;
    inline void add(int u, int v)
    {
        // std::cout << "EDGE " << u << ' ' << v << '\n';
        nxt[++ tot] = head[u];
        head[u] = tot;
        to[tot] = v; 
    }
}

int n, m, q, valteam[N], in[N];
int dfn[N], low[N], dt;
int col[N], ct;
int sck[N], st;

std::vector < int > set[N];

bool choose[N];

inline void tarjan(int u)
{
    ++ dt; dfn[u] = low[u] = dt;
    ++ st; sck[st] = u;
    for (int i = E1::head[u]; i; i = E1::nxt[i])
    {
        int v = E1::to[i];
        if (! dfn[v])
        {
            tarjan(v);  
            low[u] = std::min(low[u], low[v]); 
        }
        else low[u] = std::min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u])
    {
        ++ ct;
        while (sck[st] != u)
        {
            valteam[ct] ++; col[sck[st]] = ct; set[ct].push_back(sck[st]); st --;
        }
        valteam[ct] ++; col[sck[st]] = ct; set[ct].push_back(sck[st]); st --;
    }
}

std::queue < int > Q;

int opt[N], flg[N], vis[N], h[N], nowcase = 0;

inline void dfs(int x) {
    vis[x] = 1;
    for (int i = E1::head[x]; i; i = E1::nxt[i]) {
        int v = E1::to[i];
        if (choose[v] == 0) continue;
        if (vis[v] == 0) h[v] = h[x] + E1::val[i];
        else if (h[v] != h[x] + E1::val[i]) nowcase = 1;
        if (vis[v] == 0) dfs(v);
    }
}

inline bool check(int color) {
    nowcase = 0;
    int beg = -1;
    for (auto it : set[color])
        choose[it] = 1, beg = it;
    h[beg] = 1;
    dfs(beg);

    for (auto it : set[color])
        choose[it] = 0, vis[it] = 0;

    if (nowcase == 1) return 1;
    else return 0;
}

int main()
{
    read(n), read(m), read(q);

    for (int i = 1; i <= m; ++ i)
    {
        int u, v, b; read(u), read(v); b = v;
        if (v == 0) continue;
        u = (((u % n) + n) % n);
        v = (((u + v) % n) + n) % n;
        if (u != v)
            E1::add(u, v, b);
        else opt[u] = 1;
    }
    for (int i = 0; i < n; ++ i)
        if (! dfn[i]) tarjan(i);
    for (int i = 0; i < n; ++ i) {
        // std::cout << "col " << i << ' ' << col[i] << '\n';
        int color = col[i];
        if (opt[i] == 1 || (valteam[color] > 1 && check(color))) {
            flg[color] = 1;
        }
    }
    for (int u = 0; u < n; ++ u)
    {
        for (int i = E1::head[u]; i; i = E1::nxt[i])
        {
            int v = E1::to[i];
            if (col[u] != col[v])
            {
                E2::add(col[v], col[u]);
                in[col[u]] ++; 
            }
        }
    }

    for (int i = 1; i <= ct; ++ i)
        if (in[i] == 0) 
            Q.push(i);

    while (Q.size())
    {
        int u = Q.front(); Q.pop();
        for (int i = E2::head[u]; i; i = E2::nxt[i])
        {
            int v = E2::to[i];
            flg[v] = std::max(flg[v], flg[u]);
            in[v] --;
            if (in[v] == 0) Q.push(v);
        }
    } 
    while (q --) {
        int x; read(x);
        x = (((x % n) + n) % n);
        if (flg[col[x]] == 0) std::cout << "No\n";
        else std::cout << "Yes\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3ms
memory: 30188kb

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: 2ms
memory: 26132kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

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: