QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796623#9810. Obliviate, Then ReincarnateMYdinosaurML 4ms38680kbC++143.4kb2024-12-01 22:26:542024-12-01 22:27:01

Judging History

This is the latest submission verdict.

  • [2024-12-01 22:27:01]
  • Judged
  • Verdict: ML
  • Time: 4ms
  • Memory: 38680kb
  • [2024-12-01 22:26:54]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, ll> pa;
const int N = 5e5 + 10;
int spec = 0;
int abc[N], abcd[N], a[N];
int vis[N], dfn[N], low[N];
int cnt = 0, tot = 0;
vector <int> sdf[N];
vector <pa> v[N];
int bj[N];
int na[N];
ll f[N];
stack <int> q;


inline void read(ll &x)
{
    ll w = 1; x = 0; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') w = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + (ch ^ 48); ch = getchar();}
    x = x * w;
}

void dg(int x)
{
    vis[x] = 1;
    cnt ++;
    dfn[x] = low[x] = cnt;
    q.push(x);
    for (int i = 0; i < v[x].size(); i++)
    {
        int y = v[x][i].first;
        if (abc[y] == 1) continue;
        if (dfn[y] == 0)
        {
            dg(y);
            low[x] = min(low[x], low[y]);
        }
        else if (!bj[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        tot ++;
        a[tot] = x;
        while (!q.empty())
        {
            int t = q.top();
            q.pop();
            bj[t] = tot;
            if (t == x) break;
        }
    }
}

void dfs(int x)
{
    for (int i = 0; i < v[x].size(); i++)
    {
        int y = v[x][i].first;
        if (abc[y] == 1) 
        {
            abc[x] = abc[y];
            return;
        }
        dfs(y);
        if (abc[y] == 1) 
        {
            abc[x] = abc[y];
            return;
        }
    }
}

int work(int fa, int da)
{
    if (abc[fa] == 1) return 1;
    int ind = 0;
    queue <int> q;
    f[fa] = 0;
    q.push(fa);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < v[x].size(); i++)
        {
            int y = v[x][i].first;
            int z = v[x][i].second;
        
            // cout << x << " "  << f[x] << " " << y << " " << f[y] << " " << z << endl; 
            if (bj[y] != da) continue;
            if (abc[y] == 1) return 1;
            if (f[y] == -1) 
            {
                f[y] = f[x] + z;
                q.push(y);
            }
            else if (f[y] != f[x] + z) return 1;
        }
    }
    return 0;
}

int main()
{
    //     freopen("in.txt","r",stdin);
    // freopen("1.txt","w",stdout);
    ll n, m, qe;
    read(n); read(m); read(qe);
    for (int i = 1; i <= m; i++)
    {
        ll x, y;
        read(x); read(y);
        if (y == 0) continue;
        ll t = (x + y) % n;
        x = x % n;
        x = (x + n) % n;
        t = (t + n) % n;
        // cout << x << " " << t << " " << y << endl;
        if (x == t) 
        {
            abc[x] = 1;
        }
        else 
        {
            v[x].push_back({t, y});
        }
    }
    for (int i = 0; i < n; i++)
    {
        f[i] = -1;
        // if (abc[i] == 1) continue;
        if (!vis[i]) dg(i);
    }
    for (int i = 1; i <= tot; i++)
    {
        int x = a[i];
        na[i] = work(x, i);
    }
    for (int i = 0; i < n; i++)
    {
        if (abc[i] == 1 || na[bj[i]] == 1) abc[i] = 1;
    }
    for (int i = 0; i < n; i++)
    {
        if (abc[i] == 0) dfs(i);
    }
    for (int i = 1; i <= qe; i++)
    {
        ll x;
        read(x);
        x = x % n;
        x = (x + n) % n;
        if (abc[x] == 1) 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: 4ms
memory: 38416kb

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

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: 4ms
memory: 38680kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Memory Limit Exceeded

input:

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

output:


result: