Submission #802083

#	Time	Username	Problem	Language	Result	Execution time	Memory
802083		kirakaminski968	Toy Train (IOI17_train)	C++17	100 / 100	504 ms	1492 KiB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int> adj[5005];
vector<int> exc; 
vector<int> calc(vector<int> &a, vector<int> &v, int winner){
  vector<int> deg(n); 
  queue<int> q; 
  for(int i = 0;i<n;++i){
    if(exc[i]) continue; 
    for(auto x : adj[i]){
      if(!exc[x]) deg[x]++; 
    }
  }
  for(auto x : v){
    if(deg[x] > 0){
      deg[x] = 0; 
    }
    q.push(x); 
  }
  vector<int> res; 
  while(!q.empty()){
    int u = q.front(); q.pop(); 
    res.push_back(u); 
    for(auto x : adj[u]){
      if(exc[x]) continue; 
      if(a[x] == winner && deg[x] > 0){
        deg[x] = 0; 
        q.push(x); 
      }
      else if(a[x] != winner){
        deg[x]--; 
        if(deg[x] == 0) q.push(x); 
      }
    }
  }
  return res; 
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v){
  n = a.size(); m = u.size(); 
  vector<int> ans(n); 
  exc.resize(n); 
  for(int i = 0;i<m;++i){
    adj[v[i]].push_back(u[i]); 
  }
  while(true){
    int alive = count(exc.begin(),exc.end(),0); 
    if(alive == 0) break; 
    vector<int> R; 
    for(int i = 0;i<n;++i){
      if(!exc[i] && r[i]) R.push_back(i); 
    }
    R = calc(a,R,1); 
    if(R.size() == alive){
      for(auto x : R){
        exc[x] = 1; 
        ans[x] = 1; 
      }
    }
    else{
      vector<int> rem(n); 
      for(auto x : R) rem[x] = 1; 
      R.clear(); 
      for(int i = 0;i<n;++i){
        if(!exc[i] && !rem[i]) R.push_back(i); 
      }
      R = calc(a,R,0); 
      for(auto x : R){
        exc[x] = 1; 
        ans[x] = 0; 
      }
    }
  }
  return ans; 
}

Compilation message (stderr)

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:55:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     if(R.size() == alive){
      |        ~~~~~~~~~^~~~~~~~

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