QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788819#9810. Obliviate, Then Reincarnatewifi32767RE 2ms3832kbC++201.9kb2024-11-27 18:24:572024-11-27 18:24:58

Judging History

This is the latest submission verdict.

  • [2024-11-27 18:24:58]
  • Judged
  • Verdict: RE
  • Time: 2ms
  • Memory: 3832kb
  • [2024-11-27 18:24:57]
  • 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]){
        if (!color[(nex + cur) % n]){
            color[(nex + cur) % n] = 1;
            dfs((nex + cur) % 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(-y);
    }
    for (int i = 0; i < n; i ++){
        set<array<int, 2>> vis1;
        set<int> vis2;
        queue<array<int, 2>> que;
        que.push({i, 0});
        vis2.insert(i);
        vis1.insert({i, 0});
        while (!que.empty()){
            auto [x, y] = que.front();
            // cerr << x << ' ' << y << endl;
            que.pop();
            for (int nex : graph[x]){
                int nx = (x + nex) % n;
                int ny = (x + y * n + nex) / n;
                if (vis1.count({nx, ny})) continue;
                if (vis2.count(nx)){
                    color[nx] = 1;
                    dfs(nx);
                    break;
                }
                vis1.insert({nx, ny});
                vis2.insert(nx);
                que.push({nx, ny});
            }
        }
        // cerr << endl;
    }

    for (int i = 0; i < q; i ++){
        int x; cin >> x;
        x = (x % n + n) % n;
        if (color[x]) 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: 100
Accepted
time: 2ms
memory: 3576kb

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: 1ms
memory: 3572kb

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Runtime Error

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:


result: