QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#790131 | #9810. Obliviate, Then Reincarnate | xhytom | WA | 0ms | 3776kb | C++23 | 4.2kb | 2024-11-28 02:02:35 | 2024-11-28 02:02:35 |
Judging History
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) {
self(self, y);
low[x] = std::min(low[x], low[y]);
} else {
if (ins[y] && 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]);
}
}
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::cout << (is[bel[x]] ? "Yes" : "No") << "\n";
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
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: 3624kb
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: 3620kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3776kb
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'