QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783165#9810. Obliviate, Then Reincarnatecomp_towels_catWA 2ms5768kbC++205.1kb2024-11-26 00:22:092024-11-26 00:22:09

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 00:22:09]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 5768kb
  • [2024-11-26 00:22:09]
  • Submitted

answer

// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("omit-frame-pointer")

#include<bits/stdc++.h>
// #include<bits/extc++.h>

#define rep(a,b,c) for (int a=b;a<=c;a++)
#define repll(a,b,c) for (LL a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define perll(a,b,c) for (LL a=b;a>=c;a--)
#define repIt(it,ctner) for (auto it=ctner.begin();it!=ctner.end();it++)
#define perIt(it,ctner) for (auto it=ctner.rbegin();it!=ctner.rend();it++)
#define repAdj(i,h,ne,u) for(int i=h[u];i;i=ne[i])
#define setValue(ctner,val) memset(ctner,val,sizeof ctner)
#define all(ctner) ctner.begin(),ctner.end()

#define output(a,b,c) cout<<a<<" "<<b<<" "<<c<<"\n";


#define ft first
#define sd second
 
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
typedef long long LL;
typedef long long ll;
typedef unsigned long long ULL;
typedef unsigned long long ull;
typedef __int128 LLL;
typedef __int128 lll;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;
typedef pair<LL,int> PLI;
typedef pair<double,int> PDI;
typedef vector<int> VI;

//use cin
void LLLread(LLL &x){
    string s;cin>>s;
    x=0;int f=1;
    if(s[0]=='-') f=-1,s=s.substr(1);
    for(auto c:s) x=x*10+c-'0';
    x*=f;

}
//use cout
void LLLwrite(LLL x){
    if(x<0) cout<<'-',x=-x;
    if(x==0) cout<<0;
    vector<char> v;
    while(x) v.push_back(x%10+'0'),x/=10;
    reverse(v.begin(),v.end());
    for(auto c:v) cout<<c;
}

ostream& operator<<(ostream& os,const LLL& x){
    LLLwrite(x);
    return os;
}

istream& operator>>(istream& is,LLL& x){
    LLLread(x);
    return is;
}



//random
LL rnd(const LL &mn = 0, const LL &mx = 100) {
    LL x = mn + ((rand()<<15) + rand()) % (mx - mn + 1);
    return x;
};

//gcd
LL gcd(LL a,LL b){
    return __gcd(a,b);
}
//lcm
LL lcm(LL a,LL b){
    return a/__gcd(a,b)*b;
}






 
int _T=1;
const int N=5e5+5,M=3*N;
const LL mod1=998244353,mod2=1e9+7;
const int imod[4]={39983,39989,39979,39971};
const LL MAXLL=1e18;
const int MAXINT=1e9+1;
const long double pi=acos(-1.0);
const long double eps=1e-10; 
//const double phi=(1+sqrt(5))/2;
const string alphabet="abcdefghijklmnopqrstuvwxyz";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const LL mod=mod2;








int highbit(LL x){
    return 63-__builtin_clzll(x);
}



void init(){

}


int n,m,q;
queue<int> ans;
vector<PIL> G[N],G2[N];

//Kosaraju to get scc
bool vis[N];
int color[N],scc_cnt;

vector<int> scc[N],S;
void dfs1(int u){
    vis[u]=1;
    for(auto [v,w]:G[u]){
        if(vis[v]) continue;
        dfs1(v);
    }
    S.push_back(u);

}
void dfs2(int u){
    color[u]=scc_cnt;
    scc[scc_cnt].push_back(u);
    for(auto [v,w]:G2[u]){
        if(color[v]) continue;
        dfs2(v);
    }
}
void kosaraju(){
    rep(i,0,n-1){
        if(vis[i]) continue;
        dfs1(i);
    }
    perIt(it,S){
        if(color[*it]) continue;
        scc_cnt++;
        dfs2(*it);
    }
}

LL dist[N];
int cnt[N];

bool spfa(int u){
    queue<int> q;
    q.push(u);
    dist[u]=0;
    vis[u]=1;
    while(!q.empty()){
        u=q.front();q.pop();
        for(auto [v,w]:G[u]){
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) return 0;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}

void getans(){
    rep(i,1,scc_cnt){
        if(scc[i].size()<=1) continue;
        for(auto u:scc[i]){
            vis[u]=0;
        }
        int jud=spfa(scc[i][0]);
        for(auto u:scc[i]){
            vis[u]=1;
            dist[u]=MAXLL;
        }
        if(jud) ans.push(scc[i][0]);

    }

}

void bfs(){
    while(!ans.empty()){
        int u=ans.front();ans.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto [v,w]:G2[u]){
            if(!vis[v]){
                ans.push(v);
            }
        }
    }
}


void solve(){

    cin>>n>>m>>q;
    rep(i,1,m){
        LL a,b;
        cin>>a>>b;
        LL u=a,v=a+b,w=b;
        u=(u%n+n)%n;
        v=(v%n+n)%n;
        if(u==v){
            if(w!=0) ans.push(u);
            continue;
        }
        G[u].push_back({v,w});
        G2[v].push_back({u,w});
    }
    kosaraju();
    
    rep(i,0,n-1){
        vis[i]=1;
        dist[i]=MAXLL;
    }
    getans();
    rep(i,0,n-1){
        repIt(it,G[i]){
            LL w=it->sd;
            it->sd=-w;
        }
    }
    getans();
    rep(i,0,n-1){
        vis[i]=0;
    }
    bfs();
    rep(i,1,q){
        LL x;
        cin>>x;
        LL u=(x%n+n)%n;
        if(vis[u]) cout<<"Yes\n";
        else cout<<"No\n";
    }




}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);


    srand(time(0));





    // cin>>_T;
    init();
    rep(i,1,_T){
        
        solve();
    }


    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5704kb

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: 2ms
memory: 5768kb

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: 2ms
memory: 3784kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 5712kb

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'