Submission #428678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
428678	2021-06-15T13:47:34 Z	REALITYNB	Toy Train (IOI17_train)	C++14	11 / 100	1454 ms	99524 KB

train

#include <bits/stdc++.h>
#include "train.h"
using namespace std;
const int N = 5001 ;
vector<int> adj[N] ;
void dfs(int i , vector<int>&vis){
    vis[i]=1 ;
    for(int x: adj[i]){
        if(vis[x]==0) dfs(x,vis) ;
    }
    return ;
}
vector<int> who_wins(vector<int> a,vector<int> r,vector<int> u,vector<int>v){
    int n = a.size() ;
    for(int i=0;i<u.size();i++)adj[u[i]].push_back(v[i]) ;
    vector<vector<int>> reachable(n) ;
    for(int i=0;i<n;i++){
        reachable[i].resize(n) ;
        dfs(i,reachable[i]);
                reachable[i][i]=0 ;
        for(int x : adj[i]) if(x==i) reachable[i][i]=1;
    }
    vector<int> cycle(n) ;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(reachable[i][j]&&reachable[j][i]){
                cycle[i]=1;
            }
        }
    }
    vector<int> ans(n) ;
    for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(cycle[j]&&(reachable[i][j]||i==j)&&r[j]){
                    ans[i]=1 ;
                    break ;
                }
            }

    }
    return ans ;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int i=0;i<u.size();i++)adj[u[i]].push_back(v[i]) ;
      |                 ~^~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	386 ms	99100 KB	3rd lines differ - on the 1st token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	332 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	435 ms	99324 KB	Output is correct
2	Correct	490 ms	99420 KB	Output is correct
3	Correct	511 ms	99512 KB	Output is correct
4	Correct	1316 ms	99352 KB	Output is correct
5	Correct	1058 ms	99328 KB	Output is correct
6	Correct	941 ms	99356 KB	Output is correct
7	Correct	672 ms	99252 KB	Output is correct
8	Correct	604 ms	99288 KB	Output is correct
9	Correct	669 ms	99260 KB	Output is correct
10	Correct	654 ms	99220 KB	Output is correct
11	Correct	582 ms	99228 KB	Output is correct
12	Correct	159 ms	99184 KB	Output is correct
13	Correct	1454 ms	99352 KB	Output is correct
14	Correct	1393 ms	99416 KB	Output is correct
15	Correct	1406 ms	99492 KB	Output is correct
16	Correct	1353 ms	99524 KB	Output is correct
17	Correct	1380 ms	99360 KB	Output is correct
18	Correct	694 ms	99016 KB	Output is correct