Submission #289025

#	Time	Username	Problem	Language	Result	Execution time	Memory
289025		AlexLuchianov	Toy Train (IOI17_train)	C++14	11 / 100	11 ms	1668 KiB

train

#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(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 (stderr)

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:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int h = 0; h < g[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~
train.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     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:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int h = 0; h < depend[node].size(); h++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~
train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51