QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#785326 | #9810. Obliviate, Then Reincarnate | c201904 | WA | 4ms | 47928kb | C++14 | 2.7kb | 2024-11-26 17:31:12 | 2024-11-26 17:31:13 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-26 17:31:12]
- Submitted
answer
//This program need not to be initialized(Write this for all programs)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5;
int n,m,q;//number of floors,relocation instructions(edges),queries
int flr=0;//number of floors that appear
map<int,int>h;//mapping
struct node{
int v;
ll d;
};
vector<node>e[N];//edges
vector<int>e_opp[N];
void addedge(int x,int d){//x floor add d
if(!d)return ;
x=(x%n+n)%n;
int y=x+d;y=(y%n+n)%n;
cout<<x<<" "<<y<<" || ";
if(!h[x])h[x]=++flr;x=h[x];
if(!h[y])h[y]=++flr;y=h[y];
cout<<x<<" "<<y<<endl;
//cout<<x<<" "<<y<<" "<<d<<endl;
e[x].push_back((node){y,d});
e_opp[y].push_back(x);
//if(x==y)tag[x]=1;
return ;
}
int pts=0;//
int low[N],dfn[N],top[N],tops;
vector<int>scc[N];//strong connected component
int vis[N];
ll pe[N];//potential energy;
void dfs(int u,int tp){//tp means top
vis[u]=1;
for(int i=0;i<e[u].size();i++){
int v=e[u][i].v;
if(vis[v])continue;
if(top[v]!=tp)continue;
pe[v]=pe[u]+e[u][i].d;
}
return ;
}
int judge(int tp){//only consider pts in the scc
dfs(scc[tp][0],tp);
int sz=scc[tp].size();
for(int i=0;i<sz;i++){
int u=scc[tp][i];
for(int j=0;j<e[u].size();j++){
int v=e[u][j].v;;
if(top[v]!=tp)continue;
int d=e[u][j].d;
if(pe[v]!=(pe[u]+d))return 1;
}
}
return 0;
}
stack<int>st;
int tag[N];//is it in a non-zero scc?
void tarjan(int u){
st.push(u);
low[u]=dfn[u]=++pts;top[u]=0;//initialize
for(int i=0;i<e[u].size();i++){
int v=e[u][i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
//there suppose to be if !top[v],but this doesn't change the result
}
else if(!top[v]){//!top[v] means that v is in stack
low[u]=min(low[u],dfn[v]);//why ?
}
}
if(low[u]==dfn[u]){
top[u]=++tops;
scc[tops].push_back(u);
while(st.top()!=u){
int x=st.top();st.pop();
top[x]=tops;
scc[tops].push_back(x);
}
st.pop();
if(judge(tops)){
//cout<<u<<" "<<scc[tops].size()<<endl;
for(int i=0;i<scc[tops].size();i++){
int x=scc[tops][i];
tag[x]=1;//try not to use too long sentences.
}
}
}
}
void run_opp(int u){
//if(tag[u])return ; (initial points should not be deleted)
for(int i=0;i<e_opp[u].size();i++){
int v=e_opp[u][i];
if(tag[v])return ;
tag[v]=1;
run_opp(v);
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
int a,b;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
}
for(int i=1;i<=flr;i++){
if(!low[i])tarjan(i);
}
for(int i=1;i<=flr;i++){
if(tag[i])run_opp(i);
}
while(q--){
int x;
scanf("%d",&x);
x=(x%n+n)%n;
if(tag[h[x]])puts("Yes");
else puts("No");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 47928kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
1 2 || 1 2 2 2 || 2 2 Yes Yes No
result:
wrong answer 1st words differ - expected: 'Yes', found: '1'