QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789964#9810. Obliviate, Then ReincarnatelxllxsTL 184ms19812kbC++202.1kb2024-11-27 23:14:272024-11-27 23:14:29

Judging History

This is the latest submission verdict.

  • [2024-11-27 23:14:29]
  • Judged
  • Verdict: TL
  • Time: 184ms
  • Memory: 19812kb
  • [2024-11-27 23:14:27]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
typedef __int128 i128;
const int N=5e5+5,M=2e5+5,T=20,mod=998244353,B=131,INF=1e18,P=1000000711;
int n,m,q;
vector<pii> ne[N];
int ans[N];
void spfa1(){
    vector<int> st(n+1),dist(n+1,INF),cnt(n+1);
    queue<int> qu;
    st[n]=1;
    qu.push(n);
    dist[n]=0;
    while(qu.size()){
        int t=qu.front();
        qu.pop();
        st[t]=0;
        for(auto [u,v]:ne[t]){
            if(dist[u]>dist[t]+v){
                dist[u]=dist[t]+v;
                cnt[u]=cnt[t]+1;
                if(cnt[u]>=n)ans[u]=1;
                if(cnt[u]>2*n)break;
                if(!st[u]){
                    st[u]=1;
                    qu.push(u);
                }
            }
        }
    }
}
void spfa2(){
    vector<int> st(n+1),dist(n+1,-INF),cnt(n+1);
    queue<int> qu;
    st[n]=1;
    qu.push(n);
    dist[n]=0;
    while(qu.size()){
        int t=qu.front();
        qu.pop();
        st[t]=0;
        for(auto [u,v]:ne[t]){
            if(dist[u]<dist[t]+v){
                dist[u]=dist[t]+v;
                cnt[u]=cnt[t]+1;
                if(cnt[u]>=n)ans[u]=1;
                if(cnt[u]>2*n)break;
                if(!st[u]){
                    st[u]=1;
                    qu.push(u);
                }
            }
        }
    }
}
void solve(){
    cin>>n>>m>>q;
    while(m--){
        int a,b;
        cin>>a>>b;
        int p1=(a%n+n)%n,p2=((a+b)%n+n)%n;
        ne[p2].push_back({p1,b});
    }
    for(int i=0;i<n;i++)ne[n].push_back({i,0});
    spfa1();
    spfa2();
    while(q--){
        int x;
        cin>>x;
        int p=(x%n+n)%n;
        if(ans[p])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
}
signed main(){
    fast();
    int t=1;
//    cin>>t;
    while(t--)solve();
    return 0;
}
/*
3 2 3
1 1
-1 3
1
2
3

3 2 3
1 1
-1 0
1
2
3
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3636kb

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: 1ms
memory: 3660kb

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: 1ms
memory: 3856kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3576kb

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: 184ms
memory: 19812kb

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: