QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790691#9810. Obliviate, Then ReincarnateSSAABBEERRWA 0ms3616kbC++203.9kb2024-11-28 14:45:042024-11-28 14:45:04

Judging History

This is the latest submission verdict.

  • [2024-11-28 14:45:04]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3616kb
  • [2024-11-28 14:45:04]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using i64 = long long;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define multi int _;cin>>_;while(_--)
#define int long long
#define pb push_back
#define eb emplace_back
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
mt19937_64 mrand(chrono::steady_clock().now().time_since_epoch().count());
int rnd(int l,int r){ return mrand() % (r - l + 1) + l;}
#ifdef localfreopen
#define debug(x) cerr << #x << " = " << (x) << endl;
void test() {cerr << "\n";}
template<typename T, typename... Args> 
void test(T x, Args... args) {cerr << x << " ";test(args...);}
#else
#define debug //
#define test //
#endif
const ll MOD = 998244353;
// const ll MOD = 1e9+7;
ll ksm(ll x,ll y){ll ans=1;x%=MOD;while(y){if(y&1)ans=ans*x%MOD;x=x*x%MOD,y/=2;}return ans;}

const int P1 = 972152273, base1 = 809;
const int P2 = 905563261, base2 = 919;
const ll N = 200005;
//head



signed main()
{  
#ifdef localfreopen
    // freopen("1.in","w",stdout);
#endif
    fastio
    std::cout << std::fixed << std::setprecision(10);
    
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    std::vector<int> bel(n, -1), dfn(n, -1), ins(n, -1), low(n, -1), dep(n), ok(n);
    std::vector<int> stk;
    for (int i = 1; i <= m; i++) {
        int a, b;
        std::cin >> a >> b;
        int u = (a % n + n) % n;
        int v = ((a + b) % n + n) % n;
        int w = b;
        if(u == v) ok[u] = 1;
        // cout<<u<<" "<<v<<endl;
        adj[u].push_back({v, w});
    }
    int idx = 0, sccidx = 0;
    for (int i = 0; i < n; i++) {
        if (dfn[i] == -1) {
            auto dfs = [&](auto self, int x) -> void {
                // debug(x);
                low[x] = dfn[x] = ++idx;
                ins[x] = 1;
                stk.push_back(x);
                for (auto [y, w] : adj[x]) {
                    if (dfn[y] == -1) {
                        dep[y] = dep[x] + w;
                        self(self, y);
                        low[x] = std::min(low[x], low[y]);
                    } else {
                        if (ins[y]) {
                            if (dep[x] + w != dep[y]) {
                                // cout<<x;
                                // ok[y] = true;
                            }
                            low[x] = std::min(low[x], dfn[y]);
                        }
                    }
                }
                if (low[x] == dfn[x]) {
                    ++sccidx;
                    while (1) {
                        int u = stk.back();
                        stk.pop_back();
                        bel[u] = sccidx;
                        ins[u] = false;
                        if (u == x) break;
                    }
                }
            };
            dfs(dfs, i);
        }
    }
    const int N = sccidx;
    std::vector<std::vector<int>> e(N + 1);
    std::vector<int> is(N + 1);

    std::queue<int> que;
    for (int i = 0; i < n; i++) {
        if (ok[i]) {
            if (is[bel[i]] == 0) {
                is[bel[i]] = 1;
                que.push(bel[i]);
            }
        }
    }

    // std::exit(0);
    for (int u = 0; u < n; u++) {
        for (auto [v, w] : adj[u]) {
            e[bel[v]].push_back(bel[u]);
        }
    }

    while (!que.empty()) {
        int x = que.front();
        que.pop();
        for (auto y : e[x]) {
            if (is[y] == 0) {
                is[y] = 1;
                que.push(y);
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        int x;
        std::cin >> x;
        x = (x % n + n) % n;
    // std::exit(0);
        std::cout << (is[bel[x]] ? "Yes" : "No") << "\n";
    }



    return 0;
}

详细

Test #1:

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

input:

3 2 3
1 1
-1 3
1
2
3

output:

Yes
Yes
No

result:

ok 3 tokens

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

3 2 3
1 1
-1 0
1
2
3

output:

Yes
Yes
No

result:

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