oj.uz

답안 #65151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65151 2018-08-06T18:39:41 Z mohammad_kilani 장난감 기차 (IOI17_train) C++17
34 / 100
 308 ms 2124 KB 
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
vector< int > res , a , r , g[N] , g2[N];
int n , out[N] , out2[N] , last , vis[N] , vi;
bool have[N];

void make(int node){
	for(int i=0;i<g2[node].size();i++){
		if(res[g2[node][i]] != -1)
			continue;
		out[g2[node][i]]--;
		if(a[node] == a[g2[node][i]]){
			if(res[node] == a[node]){
				res[g2[node][i]] = a[node];
				make(g2[node][i]);
			}
			else{
				if(out[g2[node][i]] == 0){
					res[g2[node][i]] = a[node] ^ 1;
					make(g2[node][i]);
				}
			}
		}
		else{
			if(res[node] != a[node]){
				res[g2[node][i]] = a[node] ^ 1;
				make(g2[node][i]);
			}
			else{
				if(out[g2[node][i]] == 0){
					res[g2[node][i]] = a[node];
					make(g2[node][i]);
				}
			}
		}
	}
}

void make2(int node){
	for(int i=0;i<g2[node].size();i++){
		if(have[g2[node][i]]) continue;
		out2[g2[node][i]]--;
		if(out2[g2[node][i]] == 0){
			have[g2[node][i]] = true;
			make2(g2[node][i]);
			continue;
		}
		if(a[g2[node][i]] == 1){
			have[g2[node][i]] = true;
			make2(g2[node][i]);
		}
	}
}

bool DFS(int node){
	if(a[node] == 0)
		return (res[node] == 1);
	if(node == last)
		return true;
	vis[node] = vi;
	for(int i=0;i<g[node].size();i++){
		if(vis[g[node][i]] != vi && DFS(g[node][i]))
			return true;
	}
	return false;
}


std::vector<int> who_wins(std::vector<int> A, std::vector<int> R, std::vector<int> u, std::vector<int> v) {
	a = A;
	n = (int)a.size();
	r = R;
	res.resize(n , -1);
	for(int i = 0;i<(int)u.size();i++){
		g[u[i]].push_back(v[i]);
		g2[v[i]].push_back(u[i]);
		out[u[i]]++;
		out2[u[i]]++;
	}
	for(int i=0;i<n;i++){
		if(have[i]) continue;
		have[i] = r[i];
		if(have[i])
			make2(i);
	}
	for(int i=0;i<n;i++){
		if(res[i] != -1) continue;
		if(!have[i]){
			res[i] = 0;
			make(i);
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] == -1 && a[i] == 0){
			res[i] = 1;
			make(i);
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] != -1) continue;
		last = i;
		vi++;
		if(r[i]){
			for(int j = 0;j<g[i].size();j++){
				if(vis[g[i][j]] != vi && DFS(g[i][j])){
					res[i] = 1;
					break;
				}
			}
			if(res[i] != -1)			
				make(i);
		}
	}
	for(int i=0;i<n;i++){
		if(res[i] == -1)
			res[i] = 0;
	}
	return res;
}

Compilation message

train.cpp: In function 'void make(int)':
train.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g2[node].size();i++){
              ~^~~~~~~~~~~~~~~~
train.cpp: In function 'void make2(int)':
train.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g2[node].size();i++){
              ~^~~~~~~~~~~~~~~~
train.cpp: In function 'bool DFS(int)':
train.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[node].size();i++){
              ~^~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:106:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0;j<g[i].size();j++){
                  ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 1144 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 2 ms 1144 KB Output is correct
5 Incorrect 2 ms 1144 KB 3rd lines differ - on the 3rd token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 1924 KB Output is correct
2 Correct 48 ms 1936 KB Output is correct
3 Correct 97 ms 2124 KB Output is correct
4 Correct 14 ms 2124 KB Output is correct
5 Correct 20 ms 2124 KB Output is correct
6 Correct 129 ms 2124 KB Output is correct
7 Correct 22 ms 2124 KB Output is correct
8 Correct 16 ms 2124 KB Output is correct
9 Correct 14 ms 2124 KB Output is correct
10 Correct 14 ms 2124 KB Output is correct
11 Correct 17 ms 2124 KB Output is correct
12 Correct 11 ms 2124 KB Output is correct
13 Correct 16 ms 2124 KB Output is correct
14 Correct 13 ms 2124 KB Output is correct
15 Correct 23 ms 2124 KB Output is correct
16 Correct 15 ms 2124 KB Output is correct
17 Correct 14 ms 2124 KB Output is correct
18 Correct 308 ms 2124 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 2124 KB Output is correct
2 Correct 14 ms 2124 KB Output is correct
3 Correct 16 ms 2124 KB Output is correct
4 Correct 15 ms 2124 KB Output is correct
5 Correct 13 ms 2124 KB Output is correct
6 Correct 16 ms 2124 KB Output is correct
7 Correct 13 ms 2124 KB Output is correct
8 Correct 15 ms 2124 KB Output is correct
9 Correct 13 ms 2124 KB Output is correct
10 Correct 14 ms 2124 KB Output is correct
11 Correct 15 ms 2124 KB Output is correct
12 Correct 17 ms 2124 KB Output is correct
13 Correct 14 ms 2124 KB Output is correct
14 Correct 12 ms 2124 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 2124 KB Output is correct
2 Correct 16 ms 2124 KB Output is correct
3 Correct 14 ms 2124 KB Output is correct
4 Correct 12 ms 2124 KB Output is correct
5 Correct 3 ms 2124 KB Output is correct
6 Correct 8 ms 2124 KB Output is correct
7 Correct 11 ms 2124 KB Output is correct
8 Correct 10 ms 2124 KB Output is correct
9 Correct 10 ms 2124 KB Output is correct
10 Correct 5 ms 2124 KB Output is correct
11 Correct 9 ms 2124 KB Output is correct

Subtask #6
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 1144 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -