QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782348 | #9810. Obliviate, Then Reincarnate | dreamjoker | WA | 2426ms | 31568kb | C++23 | 2.9kb | 2024-11-25 19:48:57 | 2024-11-25 19:48:58 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-25 19:48:57]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
using pii = pair<ll,ll>;
const ll inf = numeric_limits<ll>::max()>>1;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n,m,Q; cin>>n>>m>>Q;
vector<vector<pii>> e(n+1);
for(int i=0;i<m;i++) {
int u,v,w; cin>>u>>w;
v=((u+w)%n+n)%n;
u=(u%n+n)%n;
e[u].push_back({w,v});
}
vector<int> dfn(n+1),low(n+1),instk(n+1),scc(n+1);
int cur=0,tot=0;
vector<vector<int>> st;
stack<int> stk;
auto tarjan=[&](auto &&self,int x)->void {
dfn[x]=low[x]=++cur;
stk.push(x); instk[x]=1;
for(auto [w,y]:e[x]) {
if(!dfn[y]) {
self(self,y);
low[x]=min(low[x],low[y]);
} else if(instk[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]) {
st.push_back({}); auto &v=st.back();
int y;
do {
y=stk.top(); stk.pop();
instk[y]=0;
v.push_back(y);
scc[y]=tot;
} while(y!=x);
tot++;
}
};
for(int i=0;i<n;i++) {
if(!dfn[i]) tarjan(tarjan,i);
}
vector<int> inque(n+1),cnt(n+1);
vector<ll> dist(n+1);
queue<int> q;
auto judge=[&](int s,int o) {
int id=scc[s];
for(int x:st[id]) {
inque[x]=0; cnt[x]=0; dist[x]=inf;
}
while(!q.empty()) q.pop();
q.push(s); dist[s]=0; inque[s]=1;
int tim=0;
while(!q.empty()) {
int u=q.front(); q.pop();
inque[u]=0;
tim++;
if(tim>=st[id].size()*100) return false;
for(auto [w,v]:e[u]) if(scc[v]==id) {
if(o) w=-w;
if(dist[v]>dist[u]+w) {
dist[v]=dist[u]+w;
cnt[v]=cnt[u]+1;
if(cnt[v]>=st[id].size()) {
return true;
}
if(!inque[v]) {
inque[v]=1;
q.push(v);
}
}
}
}
return false;
};
vector<int> flag(n+1);
for(int i=0;i<tot;i++) {
for(int x:st[i]) {
for(auto [w,y]:e[x])
if(flag[scc[y]]) {
flag[i]=1;
break;
}
if(flag[i]) break;
}
if(!flag[i]) flag[i]|=judge(st[i].back(),0);
if(!flag[i]) flag[i]|=judge(st[i].back(),1);
// cout<<"scc: "<<i<<" "<<flag[i]<<endl;
// for(int x:st[i]) cout<<x<<' ';
// cout<<endl;
}
while(Q--) {
int x; cin>>x;
x=(x%n+n)%n;
cout<<(flag[scc[x]]?"Yes":"No")<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
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: 3852kb
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: 3580kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
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: 156ms
memory: 24920kb
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: 2426ms
memory: 31568kb
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'