QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#780050 | #9810. Obliviate, Then Reincarnate | Yzm007 | WA | 8ms | 61292kb | C++14 | 3.7kb | 2024-11-25 00:16:25 | 2024-11-25 00:16:25 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-25 00:16:25]
- Submitted
answer
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<map>
#include<array>
#include<algorithm>
#include<queue>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int maxn=5e5+10,maxm=5e5+10;
int n,m,q,u,v;
int head[maxn],cnt,deg[maxn];
int low[maxn],dfn[maxn],num;
int stk[maxn],top,now;
int par[maxn],tot;
bool in[maxn];
bool ok[maxn],ok2[maxn],can;
bool vis[maxn];
ll val[maxn];
vector<int>node[maxn],g[maxn];
vector<P>f[maxn];
vector<array<int,3>>edg[maxn];
map<array<int,3>,bool>mp;
queue<int>qu;
struct edge{
int to,next,w;
}e[maxm];
void add(int u,int v,int w){
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u){
low[u]=dfn[u]=++num;
in[u]=1;
stk[++top]=u;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(in[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
tot++;
do{
now=stk[top--];
par[now]=tot;
in[now]=0;
node[tot].pb(now);
}while(now!=u);
}
}
void rdfs(int u){
for(auto &x:f[u]){
int v=x.fi,w=x.se;
if(vis[v]){
if(val[v]!=val[u]+w)can=1;
continue;
}
val[v]=val[u]+w;
vis[v]=1;
rdfs(v);
}
}
void solve(){
for(int i=1;i<=n;++i)
if(!dfn[i])dfs(i);
for(int u=1;u<=n;++u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(par[u]==par[v]){
edg[par[u]].pb({u,v,w});
}
}
}
rep(i,1,tot){
can=0;
for(auto &x:node[i]){
f[x].clear();
vis[x]=0;
}
for(auto &x:edg[i]){
int u=x[0],v=x[1],w=x[2];
//printf("i:%d u:%d v:%d w:%d\n",i,u,v,w);
f[u].pb(P(v,w));
f[v].pb(P(u,w));
}
int u=node[i][0];
vis[u]=1;
val[u]=0;
rdfs(u);
if(can){
for(auto &x:node[i]){
ok[x]=1;
}
ok2[i]=1;
}
}
rep(i,1,tot)g[i].clear();
for(int u=1;u<=n;++u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(par[u]!=par[v]){
deg[par[u]]++;
g[par[v]].pb(par[u]);
}
}
}
rep(i,1,tot){
if(!deg[i])qu.push(i);
}
while(!qu.empty()){
int u=qu.front();qu.pop();
for(auto &v:g[u]){
ok2[v]|=ok2[u];
if((--deg[v])==0){
qu.push(v);
}
}
}
// for(int i=1;i<=tot;++i){
// if(!out[i]){
// ans++;
// res=sum[i];
// }
// }
}
int main(){
scanf("%d%d%d",&n,&m,&q);
rep(i,1,m){
int w;
scanf("%d%d",&u,&w);
u=(u%n+n)%n;
v=u+w;v=(v%n+n)%n;
if(u==v && !w)continue;
if(u==v)ok[u]=1;
if(mp.count({u,v,w}))continue;
//printf("u:%d v:%d w:%d\n",u,v,w);
mp[{u,v,w}]=true;
add(u,v,w);
}
solve();
while(q--){
sci(u);
u=(u%n+n)%n;
puts(ok[u] || ok2[par[u]]?"Yes":"No");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 59212kb
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: 61292kb
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: 59024kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 8ms
memory: 58916kb
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'