QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#865644 | #9810. Obliviate, Then Reincarnate | Hanoist | WA | 101ms | 38668kb | C++14 | 3.0kb | 2025-01-21 20:44:30 | 2025-01-21 20:44:30 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<functional>
#include<utility>
#include<cassert>
using namespace std;
inline int read(){
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x * f;
}
const int N = 5e5 + 11;
int n,m,q,tt,top,cnt,head[N],stak[N],dfn[N],low[N],col[N],ecnt = -1;
int ecnt1 = -1,head1[N],in1[N],pos[N];
long long val[N];
bool vis[N],flag[N];
struct yjx{
int nxt,to;
long long c;
}e[N],e1[N];
inline void save(int x,int y,int w){
e[++ecnt] = (yjx){head[x],y,w};
head[x] = ecnt;
}
inline void save1(int x,int y,int w){
e1[++ecnt1] = (yjx){head1[x],y,w};
head1[x] = ecnt1;
++in1[y];
}
void tarjan(int now){
int i,temp;
dfn[now] = low[now] = ++tt;
stak[++top] = now;
for(i = head[now];~i;i = e[i].nxt){
temp = e[i].to;
if(!dfn[temp]){
tarjan(temp);
low[now] = min(low[now],low[temp]);
}
else if(!col[temp]) low[now] = min(low[now],low[temp]);
}
if(dfn[now] == low[now]){
col[now] = ++cnt;
pos[cnt] = now;
while(now != stak[top]){
col[stak[top--]] = cnt;
}
--top;
}
}
void dfs(int now){
int i,temp;
vis[now] = 1;
for(i = head[now];~i;i = e[i].nxt){
temp = e[i].to;
if(col[temp] != col[now]) continue;
if(vis[temp]){
if(val[temp] != val[now] + e[i].c) flag[col[now]] = 1;
continue;
}
val[temp] = val[now] + e[i].c;
dfs(temp);
}
}
void solve(){
int i;
for(i = 1;i <= cnt;i++){
val[pos[i]] = 0;
dfs(pos[i]);
}
}
void rebuild(){
int i,j,k;
for(i = 0;i < n;i++){
for(j = head[i];~j;j = e[j].nxt){
k = e[j].to;
if(col[i] != col[k]) save1(col[k],col[i],0);
}
}
}
void topo(){
queue<int> Q;
int i,now,temp;
for(i = 1;i <= cnt;i++){
if(!in1[i]) Q.push(i);
}
while(!Q.empty()){
now = Q.front();
Q.pop();
for(i = head1[now];~i;i = e1[i].nxt){
temp = e1[i].to;
if(flag[now]) flag[temp] = 1;
--in1[temp];
if(!in1[temp]) Q.push(in1[temp]);
}
}
}
int main(){
int t,i,j,x,y;
n = read(),m = read(),q = read();
memset(head1,-1,sizeof(head1));
memset(head,-1,sizeof(head));
for(i = 1;i <= m;i++){
x = read(),y = read();
x = (x % n + n) % n;
save(x,x + (y % n + n) % n,y);
}
for(i = 0;i < n;i++){
if(!dfn[i]) tarjan(i);
}
solve();
rebuild();
topo();
for(i = 1;i <= q;i++){
x = read();
if(flag[col[(x + n % n) % n]]) puts("Yes");
else puts("No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 23724kb
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: 25324kb
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: 20160kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 1ms
memory: 21960kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: 0
Accepted
time: 93ms
memory: 36152kb
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:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 500000 tokens
Test #6:
score: -100
Wrong Answer
time: 101ms
memory: 38668kb
input:
100848 500000 500000 720352587 361776806 231853504 -933882325 960971230 -83519300 -152772415 -631132247 842871215 -666621297 857194330 -754943024 -698506963 -705416545 -3551931 -927937446 628710320 -942247987 674921043 847145884 -325629529 475694308 -339363446 686789318 236702996 654762989 420412365...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'