QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#788699 | #9810. Obliviate, Then Reincarnate | Maxduan | ML | 4ms | 13840kb | C++20 | 2.1kb | 2024-11-27 17:57:41 | 2024-11-27 17:57:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
#define int long long
#define pii pair<int,int>
vector<pii>g[maxn],g2[maxn];
stack<int>st;
int dn,dfn[maxn],low[maxn];
int scc[maxn],cnt;
bool instk[maxn];
int ok[maxn];
int vis[maxn];
void tarjan(int k)
{
dfn[k]=low[k]=++dn;
st.push(k),instk[k]=1;
for(auto [len,x]:g[k])
{
if(!dfn[x])
{
tarjan(x);
low[k]=min(low[k],low[x]);
}
else if(dfn[x]&&instk[x]) low[k]=min(low[k],dfn[x]);
}
if(dfn[k]==low[k])
{
cnt++;
while(1)
{
int temp=st.top();
st.pop();
instk[temp]=0;
scc[temp]=cnt;
if(temp==k)break;
}
}
}
int dp[maxn],nows;
void dfs1(int u){
vis[u]=1;
for(auto [w,v]:g[u]){
if(scc[v]!=nows)continue;
if(vis[v]){
if(dp[v]!=dp[u]+w){
ok[nows]=1;
}
}
else{
dp[v]=dp[u]+w;
dfs1(v);
}
}
}
void dfs2(int u){
for(auto [w,v]:g2[u]){
if(!vis[v])dfs2(v);
if(ok[v])ok[u]=1;
}
}
signed main(){
int n,m,q;cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
a=(a%n+n)%n;
int nxt=(a+b)%n;
g[a].push_back({b,nxt});
}
for(int i=0;i<n;i++){
if(!dfn[i]) tarjan(i);
}
for(int i=0;i<n;i++){
for(auto [w,v]:g[i]){
if(scc[i]==scc[v])continue;
g2[scc[i]].push_back({w,scc[v]});
}
}
for(int i=0;i<n;i++){
if(vis[i])continue;
//cerr<<"i scc="<<i<<' '<<scc[i]<<'\n';
nows=scc[i];
dfs1(i);
}
for(int i=1;i<=cnt;i++){
vis[i]=0;
}
for(int i=1;i<=cnt;i++){
if(!vis[i])dfs2(i);
}
for(int i=1;i<=q;i++){
int x;cin>>x;
x=(x%n+n)%n;
if(ok[scc[x]]){
cout<<"Yes\n";
}
else cout<<"No\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 13840kb
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: 9712kb
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: 4ms
memory: 11812kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 3ms
memory: 9648kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: -100
Memory Limit Exceeded
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...