Submission #1065230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065230		KaleemRazaSyed	Toy Train (IOI17_train)	C++17	100 / 100	486 ms	1884 KiB

train

#include<bits/stdc++.h>
 
using namespace std;

const int N = 5000 + 10;
vector<int> G[N], I[N], w, dead, T, A;
int n;

vector<int> Reach(vector<int> &T, int P)
{
  vector<int> reach(n), cnt(n);

  for(int i = 0; i < n; i ++)
    for(int u : G[i])
      cnt[i] += !dead[u];
  
  queue<int> Q;
  for(int i = 0; i < n; i ++)
    if(!dead[i] && T[i])
      Q.push(i), reach[i] = 1;

  while(Q.size())
    {
      int u = Q.front();
      Q.pop();
      for(int v : I[u])
	{
	  if(dead[v]) continue;

	  cnt[v]--;
	  
	  if(A[v] ^ P)
	    {
	      if(!reach[v])
		reach[v] = 1, Q.push(v);
	    }
	  else
	    {   
	      if(cnt[v] == 0 && !reach[v])
		Q.push(v), reach[v] = 1;
	    }
	}
    }
  // cerr << "Reachability computed\n";
  return reach;
}

void buchi()
{
  while(true)
    {
      vector<int> T2 = Reach(T, 0);
      for(int &i : T2) i ^= 1;

      int cnt = 0;
      for(int i = 0; i < n; i ++)
	if(!dead[i])
	  cnt += T2[i];
      
      if(cnt == 0)
	{
	  for(int i = 0; i < n; i ++)
	    w[i] = !dead[i];
	  return;
	}
      
      vector<int> attr2 = Reach(T2, 1);
      
      for(int i = 0; i < n; i ++)
	dead[i] |= attr2[i];
    }
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
  A = a;
  n = a.size();
  dead = w = vector<int> (n);
  T = r;
  
  for(int i = 0; i < u.size(); i ++)
    {
      G[u[i]].push_back(v[i]);
      I[v[i]].push_back(u[i]);
    }
  
  buchi();
  return w;
}

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:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i = 0; i < u.size(); i ++)
      |                  ~~^~~~~~~~~~

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