QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#780050#9810. Obliviate, Then ReincarnateYzm007WA 8ms61292kbC++143.7kb2024-11-25 00:16:252024-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]
  • Judged
  • Verdict: WA
  • Time: 8ms
  • Memory: 61292kb
  • [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'