QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#790138#9810. Obliviate, Then ReincarnatexhytomTL 181ms30916kbC++234.4kb2024-11-28 02:11:542024-11-28 02:11:54

Judging History

This is the latest submission verdict.

  • [2024-11-28 02:11:54]
  • Judged
  • Verdict: TL
  • Time: 181ms
  • Memory: 30916kb
  • [2024-11-28 02:11:54]
  • 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);
    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;
        adj[u].push_back({v, w});
    }
    std::vector<int> bel(n, -1), dfn(n, -1), ins(n, -1), low(n, -1), dep(n), ok(n);
    std::vector<int> stk;
    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]) {
                    // debug(y);
                    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]) {
                                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]) {
            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: 3604kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

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: 181ms
memory: 30916kb

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: