QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789093#9810. Obliviate, Then Reincarnatewifi32767TL 0ms0kbC++202.3kb2024-11-27 19:15:172024-11-27 19:15:21

Judging History

This is the latest submission verdict.

  • [2024-11-27 19:15:21]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-11-27 19:15:17]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
const int MAX = 5e5 + 5, mod = 998244353;

vector<int> graph[MAX];
vector<int> rev_graph[MAX];
int color[MAX];
int n, m, q;
void dfs(int cur){
    for (int nex : rev_graph[cur]){
        // cerr << "_" << (nex + cur + n) % n << ' ' << nex << endl;
        if (color[(nex + cur + n) % n] != 1){
            color[(nex + cur + n) % n] = 1;
            dfs((nex + cur + n) % n);
        }
    }
}
void solve(){
    cin >> n >> m >> q;
    vector<array<int, 2>> comm;
    for (int i = 0; i < m; i ++){
        int x, y; cin >> x >> y;
        x = (x % n + n) % n;
        if (y) comm.push_back({x, y});
    }
    for (auto [x, y] : comm){
        graph[x].push_back(y);
        int pos = (x + y) % n;
        rev_graph[pos].push_back((n - (y % n)) % n);
    }
    for (int i = 0; i < n; i ++){
        if (color[i]) continue;
        set<array<int, 2>> vis1;
        set<int> vis2;
        queue<array<int, 2>> que;
        que.push({i, 0});
        vis2.insert(i);
        vis1.insert({i, 0});
        color[i] = 2;
        while (!que.empty()){
            auto [x, y] = que.front();
            // cerr << x << ' ' << y << endl;
            que.pop();
            for (int nex : graph[x]){
                int nx = ((x + nex % n) + n) % n;
                int ny = (__int128_t)(x + y * n + nex) / n;
                if (color[nx] == 1) continue;
                if (vis1.count({nx, ny})) continue;
                if (vis2.count(nx)){
                    // for (int j : vis2){
                    //     if (color[j] == 2)
                    //     color[j] = 0;
                    // }
                    color[nx] = 1;
                    dfs(nx);
                }
                vis1.insert({nx, ny});
                vis2.insert(nx);
                color[nx] = 2;
                que.push({nx, ny});
            }
        }
        // cerr << i << endl;
    }

    for (int i = 0; i < q; i ++){
        int x; cin >> x;
        x = (x % n + n) % n;
        if (color[x] == 1) yes;
        else no;
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // int T=1;cin>>T;while(T--)
    solve();
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

3 2 3
1 1
-1 3
1
2
3

output:


result: