oj.uz

답안 #427570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
427570 2021-06-14T17:18:31 Z markthitrin 장난감 기차 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -