QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791225 | #9810. Obliviate, Then Reincarnate | guodong# | WA | 0ms | 43404kb | C++17 | 3.0kb | 2024-11-28 17:32:32 | 2024-11-28 17:32:32 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define rep(x, l, r) for(int x = l; x <= r; x++)
#define clr(x, y) memset(x, y, sizeof(x))
using namespace std;
const int MAXN = 5e5 + 5;
const int INF = 1e15;
int cnt2, tot, top;
queue<int> que;
int dfn[MAXN], low[MAXN], sta[MAXN], insta[MAXN], dis[MAXN], col[MAXN], flag[MAXN];
int flag2[MAXN], ans[MAXN], c[MAXN];
struct graph{
int cnt;
int head[MAXN], nxt[MAXN], to[MAXN], value[MAXN];
void init(){
cnt = 0;
clr(head, -1);
}
void addedge(int u, int v, int w){
nxt[cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
value[cnt] = w;
cnt++;
}
} G1, G2;
void dfs(int u, int id){
for(int e = G1.head[u]; e != -1; e = G1.nxt[e]){
int v = G1.to[e];
if(col[u] != col[v]) continue;
if(dis[v] != INF){
if(dis[v] != dis[u] + G1.value[e]) flag[id] = 1;
continue;
}
dis[v] = dis[u] + G1.value[e];
dfs(v, id);
}
}
void tarjan(int u){
dfn[u] = low[u] = ++cnt2;
sta[++top] = u;
insta[u] = 1;
for(int e = G1.head[u]; e != -1; e = G1.nxt[e]){
int v = G1.to[e];
if(!dfn[v]){
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(insta[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
tot++;
do{
col[sta[top]] = tot;
insta[sta[top]] = 0;
}while(sta[top--] != u);
}
}
signed main(){
int n, m, q;
scanf("%lld%lld%lld", &n, &m, &q);
G1.init(); G2.init();
rep(i, 1, m){
int a, b;
scanf("%lld%lld", &a, &b);
int u = (a % n + n - 1) % n + 1, v = ((a + b) % n + n - 1) % n + 1;
if(u != v) G1.addedge(u, v, b);
else{
if(b) flag2[u] = 1;
}
}
rep(i, 1, n){
if(!dfn[i]) tarjan(i);
}
clr(flag, -1);
rep(i, 1, n) dis[i] = INF;
rep(i, 1, n){
if(flag[col[i]] != -1) continue;
flag[col[i]] = 0;
dis[i] = 0;
dfs(i, col[i]);
}
// puts("xxxxxxxxxx");
rep(i, 1, n) if(flag2[i]) flag[col[i]] = 1;
rep(u, 1, n){
for(int e = G1.head[u]; e != -1; e = G1.nxt[e]){
int v = G1.to[e];
if(col[u] == col[v]) continue;
G2.addedge(col[v], col[u], 0);
c[col[u]]++;
}
}
// puts("xxxxxx");
rep(i, 1, tot){
if(!c[i]) que.push(i);
ans[i] = flag[i];
}
while(!que.empty()){
int u = que.front();
que.pop();
for(int e = G2.head[u]; e != -1; e = G2.nxt[e]){
int v = G2.to[e];
ans[v] |= ans[u];
c[v]--;
if(!c[v]) que.push(v);
}
}
// puts("xxxxxxxxxx");
while(q--){
int x;
scanf("%lld", &x);
if(ans[col[x]]) puts("YES");
else puts("NO");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 43404kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
YES YES NO
result:
wrong answer 1st words differ - expected: 'Yes', found: 'YES'