QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783083 | #9810. Obliviate, Then Reincarnate | FHQY | TL | 190ms | 144240kb | C++17 | 2.7kb | 2024-11-25 23:14:22 | 2024-11-25 23:14:23 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-25 23:14:22]
- Submitted
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
const int N=1e6+5;
int n;
int vis[N],dfn[N],low[N],sk[N],top,num,cnt,col[N];
int viss[N],dis[N],cntt[N];
int in[N],out[N];
bool vs[N],fl[N];
vector<int>e[N],scc[N];
vector<pii>G[N],g[N];
void tarjan(int u){
vis[sk[++top]=u]=1;
dfn[u]=low[u]=++num;
for(auto to:G[u]){
int v=to.fi;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int v;cnt++;
do{
v=sk[top--];
vis[v]=0;
col[v]=cnt;
}while(u!=v);
}
}
bool spfa(int x,int op,vector<int> p){
int inf=1e18;
for(auto now : p)
{
viss[now]=0,dis[now]=inf*op;
}
dis[x]=0,cntt[x]=0;
queue<int> q;
q.push(x);
while(!q.empty())
{
int now = q.front();
q.pop();
viss[now]=0;
for(int i=0;i<g[now].size();i++)
{
pair<int,int> s=g[now][i];
if(col[s.first]!=col[x])continue;
// cout<<now<<' '<<s.first<<" ff"<<endl;
if(dis[s.first]>dis[now]+s.second*op)
{
dis[s.first]=dis[now]+s.second*op;
cntt[s.first]=cntt[now]+1;
if(cntt[now]>=p.size()) return true;
if(!viss[s.first]) viss[s.first]=1,q.push(s.first);
}
}
}
return false;
}
void solve(){
cin>>n;
int m,Q;
cin>>m>>Q;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
if(b==0)
continue;
a=(a%n+n)%n;
G[a+1].push_back({((a+b)%n+n)%n+1,b});
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
scc[col[i]].push_back(i);
for(int u=1;u<=n;u++){
for(auto to:G[u]){
int v=to.fi;
if(col[u]==col[v])continue;
in[col[u]]++;
out[col[v]]++;
e[col[v]].push_back(col[u]);
}
}
for(int u=1;u<=n;u++){
for(auto to:G[u]){
int v=to.fi;
if(col[u]!=col[v])continue;
g[u].push_back({v,to.se});
}
}
// for(int i=1;i<=cnt;i++){
// cout<<"# ";
// for(auto v:scc[i])
// cout<<v<<' ';
// cout<<endl;
// }
for(int i=1;i<=n;i++){
int cl=col[i];
if(vs[cl])continue;
vs[cl]=1;
fl[cl]=spfa(i,1,scc[cl])|spfa(i,-1,scc[cl]);
// cout<<i<<' '<<cl<<' '<<fl[cl]<<endl;
}
//cout<<"DEBUG"<<endl;
queue<int>q;
for(int i=1;i<=cnt;i++)
if(!in[i])q.push(i);
while(q.size()){
int u=q.front();q.pop();
for(auto v:e[u]){
fl[v]|=fl[u];
if(!--in[v])q.push(v);
}
}
while(Q--){
int x;
cin>>x;
x=(x%n+n)%n+1;
if(fl[col[x]])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return ;
}
int T=1;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// cin>>T;
for(int kase=1;kase<=T;kase++){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 114288kb
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: 11ms
memory: 113660kb
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: 11ms
memory: 109864kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 4ms
memory: 111100kb
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: 190ms
memory: 144240kb
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
Time Limit Exceeded
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...