oj.uz

Submission #427570

# Submission time Handle Problem Language Result Execution time Memory
427570 2021-06-14T17:18:31 Z markthitrin Toy Train (IOI17_train) C++14
23 / 100
 984 ms 64924 KB 
#include "train.h"
#include <vector>
#include <iostream>
int N,M;
std::vector<int> f[5005];
std::vector<int> inv_f[5005];
std::vector<int> ans;
int degree[5005];
int m[5005];
bool come[5005];
bool reachable[5005];
bool visit[5005];
void inv_bfs(std::vector<int>& a,int pos){
    if(come[pos])
        return;
    come[pos] = true;
    for(int q = 0;q<inv_f[pos].size();q++){
        m[inv_f[pos][q]]++;
        if(a[inv_f[pos][q]] == 0 && degree[inv_f[pos][q]] == m[inv_f[pos][q]]){
            inv_bfs(a,inv_f[pos][q]);
        }
        else if(a[inv_f[pos][q]] == 1)
            inv_bfs(a,inv_f[pos][q]);
    }
}
void bfs(std::vector<int>& a,int pos){
    if(visit[pos])
        return;
    visit[pos]  =true;
    for(int q = 0 ;q<f[pos].size();q++){
        if(come[f[pos][q]]){
            reachable[f[pos][q]] = true;
            bfs(a,f[pos][q]);
        }
    }
}
void last_func(std::vector<int> a,int pos){
    if(a[pos] == 0 && m[pos] != degree[pos] && !reachable[pos])
        return;
    if(ans[pos] == 1)
        return;
    ans[pos] = 1;
    for(int q = 0 ;q<inv_f[pos].size();q++){
        m[inv_f[pos][q]]++;
        last_func(a,inv_f[pos][q]);
    }
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	N = a.size();
	M = u.size();
    for(int q = 0 ;q<N;q++){
        ans.push_back(0);
    }
	for(int q = 0 ;q<M;q++){
        f[u[q]].push_back(v[q]);
        inv_f[v[q]].push_back(u[q]);
        degree[u[q]]++;
	}
	for(int q = 0;q<N;q++){
        if(r[q]){
            for(int w = 0 ;w<N;w++){
                m[w] = 0;
                come[w] = false;
                visit[w] = false;
            }
            inv_bfs(a,q);
            bfs(a,q);
        }
	}
    for(int w = 0;w<N;w++){
        m[w] = 0;
    }
	for(int q= 0;q<N;q++){
        if(reachable[q])
            last_func(a,q);
	}
	return ans;
}
/*
2 4
0 1
1 0
0 0
0 1
1 0
1 1
1 1
*/

Compilation message

train.cpp: In function 'void inv_bfs(std::vector<int>&, int)':
train.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int q = 0;q<inv_f[pos].size();q++){
      |                   ~^~~~~~~~~~~~~~~~~~
train.cpp: In function 'void bfs(std::vector<int>&, int)':
train.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int q = 0 ;q<f[pos].size();q++){
      |                    ~^~~~~~~~~~~~~~
train.cpp: In function 'void last_func(std::vector<int>, int)':
train.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int q = 0 ;q<inv_f[pos].size();q++){
      |                    ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1520 KB 3rd lines differ - on the 42nd 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 460 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 1740 KB Output is correct
2 Correct 171 ms 1740 KB Output is correct
3 Correct 236 ms 1740 KB Output is correct
4 Correct 984 ms 57808 KB Output is correct
5 Correct 185 ms 40888 KB Output is correct
6 Correct 22 ms 2892 KB Output is correct
7 Correct 441 ms 3912 KB Output is correct
8 Correct 44 ms 8328 KB Output is correct
9 Correct 8 ms 1612 KB Output is correct
10 Correct 49 ms 6436 KB Output is correct
11 Correct 31 ms 4296 KB Output is correct
12 Correct 8 ms 1356 KB Output is correct
13 Correct 78 ms 63736 KB Output is correct
14 Correct 78 ms 61520 KB Output is correct
15 Correct 82 ms 64924 KB Output is correct
16 Correct 84 ms 62452 KB Output is correct
17 Correct 79 ms 62632 KB Output is correct
18 Correct 292 ms 1356 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 10792 KB Output is correct
2 Correct 79 ms 60832 KB Output is correct
3 Correct 59 ms 36804 KB Output is correct
4 Correct 67 ms 49472 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 6 ms 972 KB Output is correct
7 Correct 9 ms 1740 KB Output is correct
8 Correct 6 ms 1100 KB Output is correct
9 Correct 11 ms 1612 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 10 ms 2892 KB Output is correct

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1520 KB 3rd lines differ - on the 42nd token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -