oj.uz

답안 #288997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
288997 2020-09-02T09:18:14 Z AlexLuchianov 장난감 기차 (IOI17_train) C++14
0 / 100
 10 ms 1792 KB 
#include "train.h"
#include <queue>
#include <iostream>

std::vector<std::vector<int>> g, depend;

int refresh(int node, std::vector<int> &own, std::vector<int> &state) {
  if(own[node] == 1) {
    for(int h = 0; h < g[node].size();h ++) {
      int to = g[node][h];
      if(state[to] == 1)
        return 1;
    }
    return 0;
  } else {
    for(int h = 0; h < g[node].size(); h++) {
      int to = g[node][h];
      if(state[to] == 0)
        return 0;
    }
    return 1;
  }
}

std::vector<int> first_phase(std::vector<int> own, std::vector<int> r) {
  int n = own.size();
  std::vector<int> state(n);
  std::queue<int> q;
  for(int i = 0; i < n; i++)
    if(r[i] == 1) {
      state[i] = 1;
      q.push(state[i]);
    }

  while(0 < q.size()) {
    int node = q.front();
    q.pop();
    for(int h = 0; h < depend[node].size(); h++) {
      int to = depend[node][h];
      if(state[to] == 0) {
        state[to] = refresh(to, own, state);
        if(state[to] == 1)
          q.push(to);
      }
    }
  }
  return state;
}

int refresh2(int node, std::vector<int> &own, std::vector<int> &state) {
  if(own[node] == 1) {
    for(int h = 0; h < g[node].size(); h++) {
      int to = g[node][h];
      if(state[to] == 0)
        return 0;
    }
    return 1;
  } else {
    for(int h = 0; h < g[node].size(); h++) {
      int to = g[node][h];
      if(state[to] == 1)
        return 1;
    }
    return 0;
  }
}

std::vector<int> second_phase(std::vector<int> &own, std::vector<int> &init) {
  int n = own.size();
  std::vector<int> state(own.size());
  std::queue<int> q;
  for(int i = 0; i < n; i++)
    if(init[i] == 0) {
      state[i] = 1;
      q.push(i);
    }
  while(0 < q.size()) {
    int node = q.front();
    q.pop();
    for(int h = 0; h < depend[node].size(); h++) {
      int to = depend[node][h];
      if(state[to] == 0) {
        state[to] == refresh2(to, own, state);
        if(state[to] == 1) {
          q.push(to);
        }
      }
    }
  }
  return state;

}

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
  
  std::vector<int> res(a.size());
  int n = a.size();
  g.clear();
  depend.clear();
  g.resize(n);
  depend.resize(n);
  for(int i = 0; i < u.size(); i++) {
    g[u[i]].push_back(v[i]);
    depend[v[i]].push_back(u[i]);
  }
  std::vector<int> state = first_phase(a, r); 
  std::vector<int> state2 = second_phase(a, state);
  for(int i = 0; i < n; i++)
    res[i] = !state2[i];
  return res;
}

Compilation message

train.cpp: In function 'int refresh(int, std::vector<int>&, std::vector<int>&)':
train.cpp:9:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for(int h = 0; h < g[node].size();h ++) {
      |                    ~~^~~~~~~~~~~~~~~~
train.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int h = 0; h < g[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> first_phase(std::vector<int>, std::vector<int>)':
train.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(int h = 0; h < depend[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
train.cpp: In function 'int refresh2(int, std::vector<int>&, std::vector<int>&)':
train.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int h = 0; h < g[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~
train.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int h = 0; h < g[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> second_phase(std::vector<int>&, std::vector<int>&)':
train.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int h = 0; h < depend[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
train.cpp:83:19: warning: value computed is not used [-Wunused-value]
   83 |         state[to] == refresh2(to, own, state);
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1280 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 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 51.0

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