QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788992 | #9810. Obliviate, Then Reincarnate | jdyt11 | ML | 5ms | 16132kb | C++23 | 2.3kb | 2024-11-27 18:58:53 | 2024-11-27 18:58:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define pll pair<ll,ll>
#define ls d*2
#define rs d*2+1
#define mid (l+r)/2
#define lowbit(x) (x&(-x))
//#define endl "\n"
#define all(x) x.begin(),x.end()
#define int long long
//mt19937 seed;
//uniform_int_distribution<int>num(0,2e9);
const int N=1e6+10;
const int M=33;
int n,m,q;
vector<pii>e[N];
vector<int>fan[N],scc[N];
int cnt,id[N],insta[N];
stack<int>s;
int low[N],dfn[N],dep;
int is[N],ans[N];
int ru[N];
bool dfs(int qi,int now,int u,vector<int>vis){
for(auto [v,w]:e[u]){
if(id[u]==id[v]&&!vis[v]){
vis[v]=1;
if(v==qi&&now+w!=0)return 1;
if(dfs(qi,now+w,v,vis))return 1;
vis[v]=0;
}
}
return 0;
}
void tarjan(int u){
dfn[u]=low[u]=++dep;
s.push(u);
insta[u]=1;
for(auto [v,w]:e[u]){
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]){
int y;
cnt++;
int tot=0;
while(1){
y=s.top();
s.pop();
insta[y]=0;
tot++;
id[y]=cnt;
if(u==y)break;
}
vector<int>vis(n+1,0);
vis[u]=1;
if((tot==1&&is[u])||(tot>1&&dfs(u,0,u,vis)))ans[cnt]=1;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int _=1;//cin>>_;
while(_--){
cin>>n>>m>>q;
int temp=1e10;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
if(b==0)continue;
int u=a+temp*n;
u%=n;
if(u==0)u=n;
int v=a+b+temp*n;
v%=n;
if(v==0)v=n;
if(u==v){
is[u]=1;
continue;
}
e[u].push_back({v,b});
fan[v].push_back(u);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int u=1;u<=n;u++){
for(int v:fan[u]){
if(id[u]!=id[v])scc[id[u]].push_back(id[v]),ru[id[v]]++;
}
}
queue<int>qq;
for(int i=1;i<=cnt;i++)if(!ru[i])qq.push(i);
while(qq.size()){
int u=qq.front();
qq.pop();
for(int v:scc[u]){
ru[v]--;
if(!ru[v])qq.push(v);
ans[v]|=ans[u];
}
}
while(q--){
int x;
cin>>x;
x=x+temp*n;
x%=n;
if(x==0)x=n;
if(ans[id[x]])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 16132kb
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: 2ms
memory: 11816kb
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: 15804kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 5ms
memory: 11708kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: -100
Memory Limit Exceeded
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...