QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1260#785685#9810. Obliviate, Then ReincarnateHCCHCorycleSuccess!2024-11-26 23:18:072024-11-26 23:18:08

Details

Extra Test:

Time Limit Exceeded

input:

100000 199998 1
0 100001
0 1
1 100001
1 1
2 100001
2 1
3 100001
3 1
4 100001
4 1
5 100001
5 1
6 100001
6 1
7 100001
7 1
8 100001
8 1
9 100001
9 1
10 100001
10 1
11 100001
11 1
12 100001
12 1
13 100001
13 1
14 100001
14 1
15 100001
15 1
16 100001
16 1
17 100001
17 1
18 100001
18 1
19 100001
19 1
20 1...

output:


result:


IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785685#9810. Obliviate, Then ReincarnateCorycle#TL 736ms41056kbC++201.7kb2024-11-26 18:48:352024-11-29 23:18:12

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int read(){
    int s=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=s*10+c-'0';c=getchar();}
    return s*f;
}
ll dis[N];
vector<int>G[N];
int n,m,Q,cnt,h[N],vis[N],ans[N];
struct edge{int to,next,dist;}d[N];
void Add(int x,int y,int z){
    // cout<<"Add: "<<x<<" "<<y<<" "<<z<<endl;
    d[++cnt]=(edge){y,h[x],z};h[x]=cnt;
    G[y].push_back(x);
}
bool SPFA(int x){
    vis[x]=1;
    for(int i=h[x];i;i=d[i].next){
        int y=d[i].to;
        if(dis[y]>dis[x]+d[i].dist){
            dis[y]=dis[x]+d[i].dist;
            if(ans[y]){vis[x]=0;return true;}
            if(vis[y]){ans[x]=1;vis[x]=0;return true;}
            if(SPFA(y)){ans[x]=1;vis[x]=0;return true;}
        }
    }
    vis[x]=0;
    return false;
}
void Solve(){
    for(int i=0;i<n;i++)dis[i]=0;
    for(int i=0;i<n;i++){
        if(ans[i])continue;
        dis[i]=0;
        SPFA(i);
    }
}
void BFS(){
    queue<int>q;
    for(int i=0;i<n;i++)if(ans[i])q.push(i);
    while(q.size()){
        int x=q.front();q.pop();
        for(auto y:G[x]){
            if(!ans[y]){
                ans[y]=1;
                q.push(y);
            }
        }
    }
}
int main(){
    n=read();m=read();Q=read();
    for(int i=1;i<=m;i++){
        int a=read(),b=read();
        if(!b)continue;
        Add((a%n+n)%n,((a+b)%n+n)%n,b);
    }
    Solve();
    for(int i=1;i<=cnt;i++)d[i].dist*=-1;
    Solve();
    BFS();
    while(Q--){
        int a=(read()%n+n)%n;
        puts(ans[a]?"Yes":"No");
    }
    return 0;
}