QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#786563 | #9810. Obliviate, Then Reincarnate | Carucao | RE | 2ms | 3724kb | C++20 | 4.5kb | 2024-11-26 22:03:03 | 2024-11-26 22:03:05 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-26 22:03:03]
- Submitted
answer
#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
#define fi first
#define se second
#define min amin
#define max amax
#define eb emplace_back
using namespace std;
using ll=long long;
using LL=__int128;
using pii=pair<int,int>;
const int N=5E5+10;
const int inf=0x3f3f3f3f;
const int p=998244353;
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>U min(const U &x,const V &y){return x<y?x:y;}
template<typename U,typename V>U max(const U &x,const V &y){return y<x?x:y;}
template<typename U,typename ...V>U min(const U &x,const V &...y){return min(x,min(y...));}
template<typename U,typename ...V>U max(const U &x,const V &...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,const V &y){return y<x?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,const V &y){return x<y?x=y,true:false;}
template<typename U,typename ...V>bool cmin(U &x,const V &...y){return cmin(x,min(y...));}
template<typename U,typename ...V>bool cmax(U &x,const V &...y){return cmax(x,max(y...));}
template<typename U,typename V>U qpow(U x,V n){U y(1);for(;n;n>>=1,x*=x)if(n&1)y*=x;return y;}
ll sqrt_floor(const ll &x){ll l=0,r=inf;while(l+1^r){ll mid=l+r>>1;(x<mid*mid?r:l)=mid;}return l;}
ll sqrt_ceil(const ll &x){ll l=-1,r=inf;while(l+1^r){ll mid=l+r>>1;(mid*mid<x?l:r)=mid;}return r;}
istream &operator>>(istream &is,LL &x){string a;is>>a;bool k=a[0]=='-';if(k)a=a.substr(1);x=0;for(char &t:a)x=x*10+t-48;if(k)x=-x;return is;}
ostream &operator<<(ostream &os,LL x){if(x<0)os<<'-',x=-x;string a;do a+=x%10|48;while(x/=10);reverse(a.begin(),a.end());return os<<a;}
mt19937 rng(time(0));
struct mint{
int x;
mint():x(){}
mint(const int &x):x(x<0?x+p:x){}
mint inv()const{return qpow(*this,p-2);}
mint operator-()const{return mint(x?p-x:x);}
mint &operator+=(const mint &t){return (x+=t.x)<p?0:x-=p,*this;}
mint &operator-=(const mint &t){return (x-=t.x)<0?x+=p:0,*this;}
mint &operator*=(const mint &t){return x=ll(x)*t.x%p,*this;}
mint &operator/=(const mint &t){return *this*=t.inv();}
mint operator+(const mint &t)const{return mint(*this)+=t;}
mint operator-(const mint &t)const{return mint(*this)-=t;}
mint operator*(const mint &t)const{return mint(*this)*=t;}
mint operator/(const mint &t)const{return mint(*this)/=t;}
operator int()const{return x;}
bool operator==(const mint &t)const{return x==t.x;}
friend mint operator+(const mint &x,const int &y){return mint(x)+=y;}
friend mint operator-(const mint &x,const int &y){return mint(x)-=y;}
friend mint operator*(const mint &x,const int &y){return mint(x)*=y;}
friend mint operator/(const mint &x,const int &y){return mint(x)/=y;}
friend mint operator+(const int &x,const mint &y){return mint(x)+=y;}
friend mint operator-(const int &x,const mint &y){return mint(x)-=y;}
friend mint operator*(const int &x,const mint &y){return mint(x)*=y;}
friend mint operator/(const int &x,const mint &y){return mint(x)/=y;}
friend istream &operator>>(istream &is,mint &t){return is>>t.x;}
friend ostream &operator<<(ostream &os,const mint &t){return os<<t.x;}
};
vector<tuple<int,int,bool>>G[N];
vector<int>to[N];
int dfn[N],low[N],tot;
int st[N],top;
int col[N],cnt;
ll h[N];
bool ans[N];
void tarjan(int u){
dfn[u]=low[u]=++tot;
st[++top]=u;
for(auto &[v,w,k]:G[u]){
if(!dfn[v]){
h[v]=h[u]+w;
tarjan(v);
cmin(dfn[u],low[v]);
}
else if(!col[v]){
k|=h[u]+w!=h[v];
cmin(dfn[u],dfn[v]);
}
}
if(dfn[u]^low[u])return;
++cnt;
do col[st[top]]=cnt;while(st[top--]^u);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,s;
cin>>n>>m>>s;
for(int i=0,x,y;i<m;++i){
cin>>x>>y;
(x%=n)<0?x+=n:0;
int t=x+y;
(t%=n)<0?t+=n:0;
G[x].eb(t,y,false);
}
for(int u=0;u<n;++u){
if(!dfn[u])tarjan(u);
int &x=col[u];
for(auto &[v,w,k]:G[u]){
int &y=col[v];
if(x^y){
to[x].eb(y);
}
else{
ans[x]|=k;
}
}
}
for(int u=1;u<=cnt;++u){
for(int &v:to[u]){
if(v>=u)exit(1);
ans[u]|=ans[v];
}
}
for(int x;s--;){
cin>>x;
(x%=n)<0?x+=n:0;
cout<<(ans[col[x]]?"Yes":"No")<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3676kb
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: 3612kb
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: 3724kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: -100
Runtime Error
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...