QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#811391#9810. Obliviate, Then Reincarnaterotcar07RE 2ms7732kbC++231.2kb2024-12-12 19:01:072024-12-12 19:01:12

Judging History

This is the latest submission verdict.

  • [2024-12-12 19:01:12]
  • Judged
  • Verdict: RE
  • Time: 2ms
  • Memory: 7732kb
  • [2024-12-12 19:01:07]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+5;
int n,m,Q;typedef long long ll;
int ins[N],dfn[N],toki,low[N],col[N],tot;ll h[N];
vector<pair<int,int>> e[N];stack<int> st;
void dfs(int p){
	dfn[p]=low[p]=++toki;ins[p]=1;st.push(p);
	for(auto [x,y]:e[p]) low[p]=min(low[p],dfn[x]?ins[x]?dfn[x]:int(1e9):(h[x]=h[p]+y,dfs(x),low[x]));
	if(dfn[p]==low[p]){
		col[p]=++tot;ins[p]=0;
		while(!st.empty()&&st.top()!=p) col[st.top()]=tot,ins[st.top()]=0,st.pop();
		st.pop();
	}
}
bool f[N];
vector<int> g[N];int deg[N];
int main(){
	std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>Q;
	for(int i=1,a,b;i<=m;i++) cin>>a>>b,a=(a%n+n)%n,e[a].emplace_back(((a+b)%n+n)%n,b);
	for(int i=0;i<n;i++) if(!dfn[i]) dfs(i);
	for(int i=0;i<n;i++)
	for(auto [x,y]:e[i]){
		if(col[i]==col[x]){
			if(h[i]+y!=h[x]) f[col[i]]=1;
		}
		else g[col[x]].push_back(col[i]),deg[col[i]]++;
	}
	queue<int> q;
	for(int i=1;i<=tot;i++) if(!deg[i]) q.push(i);
	while(!q.empty()){
		int p=q.front();q.pop();
		for(int x:g[p]){
			f[x]|=f[p];
			if(!--deg[x]) q.push(x);
		}
	}
	while(Q--){
		int x;cin>>x;
		puts(f[col[x]]?"Yes":"No");
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 7660kb

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: 2ms
memory: 7732kb

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: -100
Runtime Error

input:

1 1 1
0 1000000000
-1000000000

output:


result: