QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783217#9810. Obliviate, Then Reincarnatecomp_towels_catTL 307ms39768kbC++206.0kb2024-11-26 01:37:382024-11-26 01:37:39

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 01:37:39]
  • Judged
  • Verdict: TL
  • Time: 307ms
  • Memory: 39768kb
  • [2024-11-26 01:37:38]
  • 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(){

}


LL 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);
    }
    // rep(i,1,scc_cnt){
    //     cout<<"scc "<<i<<" : ";
    //     for(auto u:scc[i]){
    //         cout<<u<<" ";
    //     }
    //     cout<<"\n";
    // }
}

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

bool spfa(int u,int szscc){
    queue<int> q;
    q.push(u);
    dist[u]=0;
    vis[u]=1;
    // cout<<"szscc is "<<szscc<<"\n";
    while(!q.empty()){
        u=q.front();q.pop();
        vis[u]=0;
        for(auto [v,w]:G[u]){
            if(constra[v]) continue;
            if(dist[v]>dist[u]+w){
                // cout<<u<<" -> "<<v<<" is "<<w<<"\n";
                dist[v]=dist[u]+w;
                cnt[v]=cnt[u]+1;
                // cout<<v<<" : "<<dist[v]<<" "<<cnt[v]<<"\n";
                if(cnt[v]>=szscc) return 0;
                if(!vis[v]){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}
// 0 1 1000000000
// 1 0 -1000000000

void getans(){
    rep(i,1,scc_cnt){
        if(scc[i].size()<=1) continue;
        // cout<<"scc "<<i<<" : ";
        for(auto u:scc[i]){
            vis[u]=0;
            constra[u]=0;
            cnt[u]=0;
            dist[u]=MAXLL;
            // cout<<u<<" ";
        }
        // cout<<"\n";
        
        int jud=spfa(scc[i][0],scc[i].size());
        for(auto u:scc[i]){
            vis[u]=1;
            constra[u]=1;
            cnt[u]=0;
            dist[u]=MAXLL;
        }
        if(!jud){
            // cout<<scc[i][0]<<" is a good node\n";
            ans.push(scc[i][0]);
        }

    }
    // cout<<"\n";

}

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;
        // cout<<u<<" "<<v<<" "<<w<<"\n";
        if(u==v){
            if(w) ans.push(u);
            continue;
        }
        G[u].push_back({v,w});
        G2[v].push_back({u,w});
    }
    kosaraju();
    
    rep(i,0,n-1){
        int u=i;
        vis[u]=1;
        constra[u]=1;
        cnt[u]=0;
        dist[u]=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;
}


詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 7856kb

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: 0ms
memory: 7764kb

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: 8076kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 3ms
memory: 7760kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: 0
Accepted
time: 307ms
memory: 39768kb

input:

50134 500000 500000
-154428638 -283522863
-186373509 -327130969
154999046 46750274
-933523447 349415487
-437683609 140099255
864996699 -262318199
811293034 -264299324
120273173 52410685
874944410 -52048424
445049930 -803690605
-138111276 -104634331
720288580 126597671
471164416 -348777147
-356502322...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 500000 tokens

Test #6:

score: -100
Time Limit Exceeded

input:

100848 500000 500000
720352587 361776806
231853504 -933882325
960971230 -83519300
-152772415 -631132247
842871215 -666621297
857194330 -754943024
-698506963 -705416545
-3551931 -927937446
628710320 -942247987
674921043 847145884
-325629529 475694308
-339363446 686789318
236702996 654762989
420412365...

output:


result: