QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#798280#9810. Obliviate, Then ReincarnateIGVARE 81ms44044kbC++143.5kb2024-12-04 11:03:382024-12-04 11:03:40

Judging History

This is the latest submission verdict.

  • [2024-12-04 11:03:40]
  • Judged
  • Verdict: RE
  • Time: 81ms
  • Memory: 44044kb
  • [2024-12-04 11:03:38]
  • Submitted

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=0;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,0,n-1) if(sz[sum[i]] > 1) ok[i] = 1;
	rep(i,0,n-1) 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,0,n-1) if(sz[sum[i]] > 1) ok[i] = 1;
	rep(i,0,n-1) 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: 4ms
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: 4ms
memory: 36372kb

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: 3ms
memory: 34352kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 0ms
memory: 38456kb

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: 81ms
memory: 44044kb

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...

output:


result: