QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#793219#9810. Obliviate, Then ReincarnateIGVAWA 4ms34556kbC++142.7kb2024-11-29 17:42:552024-11-29 17:43:00

Judging History

This is the latest submission verdict.

  • [2024-11-29 17:43:00]
  • Judged
  • Verdict: WA
  • Time: 4ms
  • Memory: 34556kb
  • [2024-11-29 17:42:55]
  • 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));  
}  
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);
}

void solve(){
	init();
    read(n);read(m);read(q);
	rep(i,0,n) ok[i] = 0;
    rep(i,1,m){
        int x,y;
		read(x);read(y);
		x = (x % n + n) % n;
		if(y == 0) continue;
		if(y % n == 0){
			ok[x] = 1;
			continue;
		}
		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: 32280kb

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

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: 32320kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 4ms
memory: 34556kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
Yes
No

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'