CSES - Datatähti 2024 loppu - Results
Submission details
Task:Peli
Sender:maweiyin24562
Submission time:2024-01-20 16:49:05 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#20.97 s1, 2details
#3--2details
#40.96 s1, 2details
#50.96 s1, 2details
#6--2details
#7--2details
#80.71 s1, 2details
#90.81 s2details
#100.82 s2details

Compiler report

input/code.cpp: In function 'void solveBF()':
input/code.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         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;


vector<int>to[100009];
int n,m,quest;

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

bool ans[100009];
bool mark[100009];

queue<Node>q;
void solveBF(){
    for(int i=1;i<=quest;i++){
        int from,end,len;
        cin>>from>>end>>len;
        Node tmp;
        tmp.pos=from;
        tmp.ed=end;
        tmp.stp=0;
        tmp.tot=len;
        tmp.qid=i;
        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>>quest;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        to[u].push_back(v);
        to[v].push_back(u);
    }
    solveBF();
    for(int i=1;i<=quest;i++){
        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
(empty)

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
(empty)

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
(empty)

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)