QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#798277 | #9810. Obliviate, Then Reincarnate | IGVA | RE | 84ms | 43188kb | C++14 | 3.5kb | 2024-12-04 11:00:43 | 2024-12-04 11:00:44 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define dep(i,a,b) for(int i=(a),i##_end=(b);i>=i##_end;--i)
using namespace std;
template<class T>inline T mymin(T x,T y){return x<y?x:y;}
template<class T>inline T mymax(T x,T y){return x>y?x:y;}
template <typename T>
inline void read(T &X){
X=0;int w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
if(w) X=-X;
}
const int maxn = 5e5 + 5;
//const double pi = acos(-1.0);
//const double eps = 1e-9;
//const int mo = 1e9 + 7;
int n,m,k,q;
int a[maxn],c[maxn];
int ans,tmp,cnt;
int flag;
char s[maxn];
bool ok[maxn];
vector<int>vc[maxn];
queue<int>Q;
int num;
int l,he[maxn],ru[maxn],chu[maxn],low[maxn],dfn[maxn],sz[maxn];
int pre[maxn],f,sta[maxn],j,ti;
int t,h,sum[maxn];
bool us[maxn];
struct node{
int v,nex;
bool vis;
}e[maxn];
void init(){
t=0;cnt=0;f=0;ti=0;
memset(he,-1,sizeof(he));
memset(ru,0,sizeof(ru));
memset(dfn,0,sizeof(dfn)); //注意
memset(us,0,sizeof(us));
memset(sum,0,sizeof(sum));
rep(i,0,n) sz[i] = 0;
}
void add(int u,int v)
{
e[t].v=v;
e[t].vis=0;
e[t].nex=he[u];
he[u]=t++;
}
void tar(int k)
{
low[k]=dfn[k]=++ti;
us[k]=1;
sta[++f]=k;
for(int i=he[k];i!=-1;i=e[i].nex)
{
int v=e[i].v;
if(!dfn[v])
{
tar(v);
low[k]=min(low[k],low[v]);
}
else if(us[v]) low[k]=min(low[k],dfn[v]);
}
if(low[k]==dfn[k])
{
cnt++;
do{
j=sta[f--];
us[j]=0;
sum[j]=cnt;
sz[cnt]++;
}while(j!=k);
}
}
void sol()
{
for(int i=1;i<=n;i++)
if(!dfn[i]) tar(i);
}
int X[maxn],Y[maxn];
void solve(){
init();
read(n);read(m);read(q);
rep(i,0,n) ok[i] = 0;
int ct = 0;
rep(i,1,m){
int x,y;
read(x);read(y);
if(y == 0) continue;
if(y % n == 0){
x = (x % n + n) % n;
ok[x] = 1;
continue;
}
if(y > 0){
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
add(nxt,x);
continue;
}
X[++ct] = x;
Y[++ct] = y;
}
sol();
rep(i,1,n) if(sz[sum[i]] > 1) ok[i] = 1;
rep(i,1,n) if(ok[i]){
Q.push(i);
while(!Q.empty()){
int x = Q.front();Q.pop();
for(int j=he[x];j!=-1;j=e[j].nex) {
int v = e[j].v;
if(!ok[v]){
ok[v] = 1;
Q.push(v);
}
}
}
}
// rep(i,1,n) cout<<"debug: "<<i<<" "<<ok[i]<<endl;
init();
rep(i,1,ct){
int x = X[i];
int y = Y[i];
x = (x % n + n) % n;
y = (y % n + n) % n;
int nxt = (x + y) % n;
add(nxt,x);
}
sol();
rep(i,1,n) if(sz[sum[i]] > 1) ok[i] = 1;
rep(i,1,n) if(ok[i]){
Q.push(i);
while(!Q.empty()){
int x = Q.front();Q.pop();
for(int j=he[x];j!=-1;j=e[j].nex) {
int v = e[j].v;
if(!ok[v]){
ok[v] = 1;
Q.push(v);
}
}
}
}
rep(i,1,q){
int x;
read(x);
x = (x % n + n) % n;
if(ok[x]) puts("Yes");
else puts("No");
}
// printf("%d\n",ans);
}
int main(){
//cin.tie(0)->sync_with_stdio(false);
int T=1,cas=1;
//read(T);
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 36400kb
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: 36396kb
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: 4ms
memory: 34352kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 6ms
memory: 38336kb
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: 84ms
memory: 43188kb
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
Runtime Error
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...