oj.uz

Submission #429080

# Submission time Handle Problem Language Result Execution time Memory
429080 2021-06-15T17:15:31 Z REALITYNB Toy Train (IOI17_train) C++17
11 / 100
 2000 ms 197732 KB 
#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,bool flg , vector<int>& r ){
    vis[i]=1 ;
    for(int x: adj[i]){
        if(flg){
            if(vis[x]==0&&r[x]==0){
                dfs(x,vis,flg,r);
            }
            continue ;
        }
        if(vis[x]==0) dfs(x,vis,flg,r) ;
    }
    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],0,r);
                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<vector<int>> reachablee(n) ;
    for(int i=0;i<n;i++){
        reachablee[i].resize(n);
        if(r[i]) continue ;
        dfs(i,reachablee[i],1,r) ;
        reachablee[i][i]=0;
        for(int x: adj[i]) if(x==i) reachablee[i][i]=1 ;
    }
    ////////////
    vector<int> cyclee(n) ;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(reachablee[i][j]&&reachablee[j][i]){
                cyclee[j]=1;
            }
        }
    }


    ////////////
    vector<int> ans(n,1) ;
    for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(adj[j].empty()&&(reachable[i][j]||i==j)){
                    ans[i]=0;
                    break;
                }
                if(cyclee[j]&&(reachable[i][j]||i==j)){
                    ans[i]=0 ;
                    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:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     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 526 ms 197188 KB 3rd lines differ - on the 14th token, expected: '1', found: '0'
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 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 197732 KB Output is correct
2 Correct 534 ms 197560 KB Output is correct
3 Correct 469 ms 197532 KB Output is correct
4 Execution timed out 2074 ms 194728 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1184 ms 197244 KB Output is correct
2 Correct 575 ms 197272 KB Output is correct
3 Correct 839 ms 197316 KB Output is correct
4 Correct 808 ms 197364 KB Output is correct
5 Correct 1180 ms 197260 KB Output is correct
6 Correct 1063 ms 197344 KB Output is correct
7 Correct 1057 ms 197268 KB Output is correct
8 Correct 792 ms 197368 KB Output is correct
9 Correct 250 ms 197140 KB Output is correct
10 Correct 1418 ms 197624 KB Output is correct
11 Correct 1379 ms 197388 KB Output is correct
12 Correct 1398 ms 197468 KB Output is correct
13 Correct 1533 ms 197496 KB Output is correct
14 Correct 1034 ms 197376 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 175532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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