QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788805#9810. Obliviate, Then Reincarnatewifi32767WA 2ms3836kbC++201.9kb2024-11-27 18:22:012024-11-27 18:22:03

Judging History

This is the latest submission verdict.

  • [2024-11-27 18:22:03]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3836kb
  • [2024-11-27 18:22:01]
  • 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 + nex * n + y) / 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: 1ms
memory: 3836kb

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: 2ms
memory: 3612kb

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3572kb

input:

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

output:

No
Yes
No

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'