QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782643#9810. Obliviate, Then ReincarnateA_J1eWA 3ms13764kbC++232.3kb2024-11-25 20:50:202024-11-25 20:50:20

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-25 20:50:20]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 13764kb
  • [2024-11-25 20:50:20]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using i32 = int;
using i64 = long long;
using i128 = __int128;
#define int long long
const int N = 5e5 + 10;
#define endl "\n"
int n, m, q;
vector<pair<int, int>> e[N];
int low[N] , num[N] , dfn;
int scc[N] , sta[N], top;
int cnt;
vector<int > e2[N];
void dfs(int u )
{
    sta[top++] = u;
    low[u] = num[u] = ++dfn;
    for(auto i : e[u])
    {
        int v = i.first;
        int val = i.second;
        if(!num[v])
        {
            dfs(v);
            low[u] = min(low[v] , low[u]);
        }
        else if(!scc[v])
            low[u] = min(low[u] , num[v]);
    }
    if(low[u] == num[u])
    {
        cnt++;
        while(1)
        {
            int v = sta[--top];
            scc[v] = cnt;
            if(u == v) break;
        }
    }
}
void tarjin(int u)
{
    cnt = top = dfn = 0;
    for(int i = 0 ; i < n ; i++)
        scc[i] = num[i] = low[i] = 0;
    for(int i = 0 ; i < n ; i++)
        if(!num[i])
            dfs(i);
}
int w[N];
bool ok[N];
bool ok2[N];
void solve()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        int u = ((a % n) + n) % n  , v = ((u + b) % n + n) % n;
        e[u].push_back({v , b});
        if(b != 0)
        e2[v].push_back(u);
    }
    tarjin(0);
    for(int i = 0 ; i < n ; i++)
        for(auto tmp : e[i])
        {
            int u = i;
            int v = tmp.first;
            int val = tmp.second;
            if(scc[u] == scc[v]) w[scc[u]] += val;
        }
    for(int i = 1 ; i <= cnt ; i++)
        if(w[scc[i]] != 0) ok2[i] = 1;
    for(int i = 0 ; i < n ; i++)
        if(ok2[scc[i]]) ok[i] = 1;
    queue<int > qq;
    for(int i = 0 ; i < n ; i++)
        if(ok[i])
            qq.push(i);
    while(!qq.empty())
    {
        int u = qq.front();
        qq.pop();
        for(int v : e2[u])
            if(!ok[v])
                ok[v] = 1 , qq.push(v);
    }
    while (q--)
    {
        int tmp;
        cin >> tmp;
        tmp = ((tmp % n) + n) % n;
        if (ok[tmp])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    i32 t = 1;
    while (t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 13764kb

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

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 11804kb

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

wrong answer 1st words differ - expected: 'Yes', found: 'No'