QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782942 | #9810. Obliviate, Then Reincarnate | ccpy# | WA | 2ms | 5948kb | C++20 | 2.6kb | 2024-11-25 22:19:42 | 2024-11-25 22:19:44 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-25 22:19:42]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 500005
int n,m,Q;
#define pll pair<ll,ll>
#define fi first
#define se second
vector<pll> e[MAX];
int dfn[MAX],low[MAX],sz;
int st[MAX],top;
int group[MAX],gr;
void tarjan(int now){
dfn[now]=low[now]=++sz;
st[++top]=now;
for(auto o:e[now]){
ll to=o.fi;
if(!dfn[to]){
tarjan(to);
low[now]=min(low[now],low[to]);
}else if(!group[to]) low[now]=min(low[now],dfn[to]);
}
if(dfn[now]==low[now]){
group[now]=++gr;
//cout<<"gr:"<<now<<" ";
while(st[top]!=now){
group[st[top]]=gr;
cout<<st[top]<<" ";
top--;
}
//cout<<endl;
top--;
}
}
int go[MAX];
ll d[MAX];bool vis[MAX];
void dfs(int x,int col){
vis[x]=1;st[++top]=x;
for(auto o:e[x]){
int y=o.fi;
if(vis[y]||group[y]!=col) continue;
d[y]=d[x]+o.se;
dfs(y,col);
}
}
int ck(int x,int col){
top=0;
dfs(x,col);
bool fl=1,fl2=0;
for(int i=1;i<=top;i++){
int a=st[i];
for(auto o:e[a]) {
int b=o.fi;
if(group[b]!=col) continue;
if(d[b]!=d[a]+o.se) fl=0;
fl2=1;
}
}
//cout<<x<<" "<<col<<" "<<fl<<" "<<fl2<<endl;
return fl!=1&&fl2;
}
vector<int> E[MAX];
int deg[MAX];
void ins(int x,int y){
E[y].push_back(x);deg[x]++;
}
void sol(){
cin>>n>>m>>Q;
for(int i=1,a,b;i<=m;i++){
cin>>a>>b;
a=(a%n+n)%n;
int nt=((a+b)%n+n)%n;
//cout<<a<<" "<<nt<<" "<<b<<endl;
e[a].push_back({nt,b});
}
for(int i=0;i<n;i++) if(!dfn[i]) tarjan(i);
for(int i=0;i<n;i++){
if(!vis[i]){
go[group[i]]=ck(i,group[i]);
}
}
//for(int i=0;i<n;i++) cout<<i<<" "<<group[i]<<" "<<go[group[i]]<<endl;
for(int i=0;i<n;i++){
for(auto o:e[i]){
if(group[i]!=group[o.fi])
ins(group[i],group[o.fi]);
}
}
queue<int> q;
for(int i=1;i<=gr;i++)
if(!deg[i]) q.push(i);
while(!q.empty()){
int x=q.front();q.pop();
for(auto y:E[x]){
go[y]|=go[x];
deg[x]--;
if(!deg[x]) q.push(x);
}
}
for(int i=1,x;i<=Q;i++){
cin>>x;
x=(x%n+n)%n;
if(go[group[x]]){
cout<<"Yes\n";
}else cout<<"No\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
while(t--) sol();
}
// g++ a.cpp -Wl,--stack=10000000 -o a && a < in.txt > out.txt
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5648kb
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: 5948kb
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: 2ms
memory: 5584kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 5704kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
1 No No No
result:
wrong answer 1st words differ - expected: 'No', found: '1'