QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782942#9810. Obliviate, Then Reincarnateccpy#WA 2ms5948kbC++202.6kb2024-11-25 22:19:422024-11-25 22:19:44

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-25 22:19:44]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 5948kb
  • [2024-11-25 22:19:42]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 500005
int n,m,Q;
#define pll pair<ll,ll>
#define fi first
#define se second
vector<pll> e[MAX];
int dfn[MAX],low[MAX],sz;
int st[MAX],top;
int group[MAX],gr;
void tarjan(int now){
	dfn[now]=low[now]=++sz;
	st[++top]=now;
	for(auto o:e[now]){
		ll to=o.fi;
		if(!dfn[to]){
			tarjan(to);
			low[now]=min(low[now],low[to]);
		}else if(!group[to]) low[now]=min(low[now],dfn[to]);
	}
	if(dfn[now]==low[now]){
		group[now]=++gr;
        //cout<<"gr:"<<now<<" ";
		while(st[top]!=now){
			group[st[top]]=gr;
            cout<<st[top]<<" ";
			top--;
		}
        //cout<<endl;
		top--;
	}
} 
int go[MAX];
ll d[MAX];bool vis[MAX];

void dfs(int x,int col){
    vis[x]=1;st[++top]=x;
    for(auto o:e[x]){
        int y=o.fi;
        if(vis[y]||group[y]!=col) continue;
        d[y]=d[x]+o.se;
        dfs(y,col);
    }
}
int ck(int x,int col){
    top=0;
    dfs(x,col);
    bool fl=1,fl2=0;
    for(int i=1;i<=top;i++){
        int a=st[i];
        for(auto o:e[a]) {
            int b=o.fi;
            if(group[b]!=col) continue;
            if(d[b]!=d[a]+o.se) fl=0;
            fl2=1;
        }
    }
    //cout<<x<<" "<<col<<" "<<fl<<" "<<fl2<<endl;
    return fl!=1&&fl2;
}
vector<int> E[MAX];
int deg[MAX];
void ins(int x,int y){
    E[y].push_back(x);deg[x]++;
}
void sol(){
    cin>>n>>m>>Q;
    for(int i=1,a,b;i<=m;i++){
        cin>>a>>b;
        a=(a%n+n)%n;
        int nt=((a+b)%n+n)%n;
        //cout<<a<<" "<<nt<<" "<<b<<endl;
        e[a].push_back({nt,b});
    }
    for(int i=0;i<n;i++) if(!dfn[i]) tarjan(i);
    for(int i=0;i<n;i++){
        if(!vis[i]){
            go[group[i]]=ck(i,group[i]);
        }
    }
    //for(int i=0;i<n;i++) cout<<i<<" "<<group[i]<<" "<<go[group[i]]<<endl;
    for(int i=0;i<n;i++){
        for(auto o:e[i]){
            if(group[i]!=group[o.fi]) 
                ins(group[i],group[o.fi]);
        }
    }
    queue<int> q;
    for(int i=1;i<=gr;i++)
        if(!deg[i]) q.push(i);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(auto y:E[x]){
            go[y]|=go[x];
            deg[x]--;
            if(!deg[x]) q.push(x);
        }
    }
    for(int i=1,x;i<=Q;i++){
        cin>>x;
        x=(x%n+n)%n;
        if(go[group[x]]){
            cout<<"Yes\n";
        }else cout<<"No\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    while(t--) sol();
}
// g++ a.cpp -Wl,--stack=10000000 -o a && a < in.txt > out.txt 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5648kb

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 5704kb

input:

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

output:

1 No
No
No

result:

wrong answer 1st words differ - expected: 'No', found: '1'