QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789036 | #9810. Obliviate, Then Reincarnate | ucup-team4352 | Compile Error | / | / | Python3 | 1.9kb | 2024-11-27 19:07:06 | 2024-11-27 19:07:07 |
Judging History
This is the latest submission verdict.
- [2024-11-27 19:07:07]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-11-27 19:07:06]
- Submitted
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=5e5+5;
vector<pii>e[maxn];
vector<int>ed[maxn];
int dfn[maxn],low[maxn],cnt;
int inst[maxn],scc[maxn],sc;
int fl[maxn],ans[maxn];
vector<int>ins[maxn],stk;
void dfs(int x){
dfn[x]=low[x]=++cnt;
inst[x]=1;
stk.push_back(x);
for(auto t:e[x]){
int u=t.first;
if(!dfn[u]){
dfs(u);
low[x]=min(low[x],low[u]);
}
else if(inst[u])low[x]=min(low[x],dfn[u]);
}
if(low[x]==dfn[x]){
sc++;
while(1){
int u=stk.back();
inst[u]=0;
scc[u]=sc;
ins[sc].push_back(u);
stk.pop_back();
if(u==x)break;
}
}
}
ll dis[maxn];
int vis[maxn],T;
void dfs2(int x){
vis[x]=1;
for(auto t:e[x]){
int u=t.first,w=t.second;
if(scc[u]!=scc[x])continue;
if(vis[u]){
if(dis[u]!=dis[x]+w)fl[T]=1;
continue;
}
dis[u]=dis[x]+w;
dfs2(u);
}
}
int deg[maxn];
void solve(){
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>w;
u=(u%n+n-1)%n+1;
v=((u+w)%n+n-1)%n+1;
e[u].push_back({v,w});
// cout<<u<<" "<<v<<" "<<w<<"\n";
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfs(i);
}
}
for(int i=1;i<=sc;i++){
T=i;
dfs2(ins[i][0]);
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
for(auto t:e[i]){
int u=t.first;
if(scc[u]!=scc[i]){
ed[scc[u]].push_back(scc[i]);
deg[scc[i]]++;
}
}
}
queue<int>qu;
for(int i=1;i<=sc;i++){
if(deg[i]==0)qu.push(i);
}
while(!qu.empty()){
int x=qu.front();
qu.pop();
for(auto u:ed[x]){
deg[u]--;
fl[u]|=fl[x];
if(deg[u]==0){
qu.push(u);
}
}
}
for(int i=1;i<=q;i++){
int x;
cin>>x;
x=(x%n+n-1)%n+1;
if(fl[scc[x]])cout<<"Yes\n";
else cout<<"No\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
詳細信息
File "answer.code", line 4 using namespace std; ^^^^^^^^^ SyntaxError: invalid syntax