CSES - Datatähti 2024 loppu - Results
Submission details
Task:Peli
Sender:maweiyin24562
Submission time:2024-01-20 16:24:31 +0200
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#20.96 s1, 2details
#30.96 s2details
#40.96 s1, 2details
#50.96 s1, 2details
#60.96 s2details
#70.97 s2details
#80.70 s1, 2details
#90.72 s2details
#100.72 s2details

Compiler report

input/code.cpp: In function 'void solve(Node)':
input/code.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i=0;i<to[u].size();i++){
      |                     ~^~~~~~~~~~~~~

Code

#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>

using namespace std;

typedef long long ll;
typedef long double ld;

vector<ll>to[100009];
ll n,m;

struct Node{
    int pos;
    int stp;
    int ed;
    int tot;
    int qid;
};

ll Q;
ll qS[100009];
ll qE[100009];
ll qC[100009];
bool ans[100009];
bool mark[100009];

queue<Node>q;
void solve(Node tmp){
    q.push(tmp);
    while(!q.empty()){
        Node now=q.front();
        q.pop();
        if(mark[now.qid]){
            continue;
        }
        int u=now.pos;
        if(now.stp==now.tot){
            if(u==now.ed){
                ans[now.qid]=true;
                mark[now.qid]=true;
            }
            continue;
        }
        for(int i=0;i<to[u].size();i++){
            int v=to[u][i];
            Node nxt;
            nxt.ed=now.ed;
            nxt.qid=now.qid;
            nxt.tot=now.tot;
            nxt.pos=v;
            nxt.stp=now.stp+1;
            q.push(nxt);
        }
    }
}

int main(){
    cin>>n>>m>>Q;
    for(ll i=1;i<=m;i++){
        ll u,v;
        cin>>u>>v;
        to[u].push_back(v);
        to[v].push_back(u);
    }

    for(ll i=1;i<=Q;i++){
        cin>>qS[i]>>qE[i]>>qC[i];
        Node tmp;
        tmp.pos=qS[i];
        tmp.ed=qE[i];
        tmp.stp=0;
        tmp.tot=qC[i];
        tmp.qid=i;
        solve(tmp);
        if(ans[i])cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
        
    }

    return 0;
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
2 1 100
1 2
1 1 0
1 2 0
2 1 0
...

correct output
YES
NO
NO
YES
NO
...

user output
YES
NO
NO
YES
NO
...
Truncated

Test 2

Group: 1, 2

Verdict:

input
50 49 100
33 34
7 8
49 50
47 48
...

correct output
NO
NO
NO
NO
NO
...

user output
NO

Test 3

Group: 2

Verdict:

input
2500 2499 100000
821 822
2351 2352
752 753
832 833
...

correct output
NO
YES
YES
NO
NO
...

user output
(empty)

Test 4

Group: 1, 2

Verdict:

input
12 12 100
9 10
2 3
1 12
1 2
...

correct output
NO
NO
NO
NO
NO
...

user output
NO

Test 5

Group: 1, 2

Verdict:

input
11 11 100
10 11
7 8
1 2
5 6
...

correct output
YES
YES
YES
YES
YES
...

user output
YES

Test 6

Group: 2

Verdict:

input
2500 2500 100000
1936 1937
1884 1885
751 752
831 832
...

correct output
NO
YES
YES
NO
NO
...

user output
(empty)

Test 7

Group: 2

Verdict:

input
2499 2499 100000
821 822
2351 2352
752 753
832 833
...

correct output
YES
YES
YES
YES
YES
...

user output
(empty)

Test 8

Group: 1, 2

Verdict:

input
50 99 100
40 47
34 50
44 47
15 16
...

correct output
YES
YES
YES
YES
YES
...

user output
(empty)

Test 9

Group: 2

Verdict:

input
2500 4999 100000
1191 2361
251 399
1026 2300
82 1655
...

correct output
YES
YES
YES
YES
YES
...

user output
(empty)

Test 10

Group: 2

Verdict:

input
2500 4999 100000
2023 2218
23 51
1020 1272
11 114
...

correct output
YES
YES
YES
YES
YES
...

user output
(empty)