oj.uz

Submission #1061375

# Submission time Handle Problem Language Result Execution time Memory
1061375 2024-08-16T08:25:06 Z vjudge1 Toy Train (IOI17_train) C++17
5 / 100
 754 ms 26080 KB 
// #include "train.h"
#include<bits/stdc++.h>
 
using namespace std;

const int N = 5000 + 10;
vector<int> G[N], I[N];
bool good[N], dead[N];
bool R[N], seen[N][N];
vector<int> st;
bool S[N];
int scc[N];

int n;

bool dfs(int v, int s)
{
  seen[v][s] = true;
  if(good[v]) return 1;

  bool ok = 0;
  for(int u : G[v])
    {
      if(seen[u][s]) continue;
      ok |= dfs(u, s);
    }
  return ok;
}

void dfs_scc(int v)
{
  S[v] = true;
  for(int u : G[v])
    if(!S[u] && !dead[u])
      dfs_scc(u);
  st.push_back(v);
}

void dfs_inv_scc(int v, int sc)
{
  S[v] = true;
  scc[v] = sc;
  for(int u : I[v])
    if(!S[u] && !dead[u])
      dfs_inv_scc(u, sc);
}

void find_good()
{
  for(int i = 0; i < n; i ++)
    S[i] = false, I[i].clear(), scc[i] = -1;
  
  for(int i = 0; i < n; i ++)
    {
      for(int u : G[i])
	I[i].push_back(u);
      if(dead[i]) continue;
      dfs_scc(i);
    }

  for(int i = 0; i < n; i ++) S[i] = false;

  while(st.size())
    {
      int u  = st.back();
      st.pop_back();
      if(S[u]) continue;
      dfs_inv_scc(u, u);
    }
}

vector<int> Arezou()
{
  vector<int> w(n);
  find_good();
  // a vertex is good if in its scc we have one charged vertex and at least have 1 edge

  int e[n] = {}, ch[n] = {};
  for(int i = 0; i < n; i ++)
    {
      ch[scc[i]] += R[i];
      for(int u : G[i])
	if(scc[i] == scc[u])
	  e[scc[i]]++;
    }

  for(int i = 0; i < n; i++)
    good[i] = (ch[scc[i]] > 0 && e[scc[i]] > 0);
  
  for(int s = 0; s < n; s++)
    w[s] = dfs(s, s);
  return w;
}

vector<int> Borzou()
{
  for(int i = 0; i < n; i ++)
    dead[i] = R[i];
  
  vector<int> w(n);
  find_good();

  int e[n] = {};
  
  for(int i = 0; i < n; i ++)
    {
      if(dead[i]) continue;
      for(int u : G[i])
	if(scc[i] == scc[u])
	  e[scc[i]]++;      
    }

  for(int i = 0; i < n; i ++)
    if(!dead[i])
      good[i] = (e[scc[i]] > 0);
  
  for(int s = 0; s < n; s++)
    w[s] = !dfs(s, s);
  return w;
}


vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
  n = a.size();

  for(int i = 0; i < n; i ++)
    {
      G[i].clear(), I[i].clear();
      R[i] = S[i] = good[i] = dead[i] = false;
      for(int j  = 0; j < n; j ++)
	seen[i][j] = false;
    }
  
  for(int i = 0; i < u.size(); i ++)
    G[u[i]].push_back(v[i]);
  

  for(int i = 0; i < n; i ++)
    R[i] = r[i];
  
  vector<int> w(n);
  int c = count(a.begin(), a.end(), 1);

  //if(c == a.size())
  //return Arezou();
  if(c == 0)
    return Borzou();

  for(int i = 0; i < n; i++)
    {
      int s = i;
      while(true)
	{
	  // do I have a cycle
	  bool cycle = false;
	  for(int c : G[s])
	    if(c == s) cycle = true;

	  if(cycle)
	    {
	      if(G[s].size() == 1)
		{
		  w[i] = r[s];
		  break;
		}
	      
	      if(r[s])
		{
		  if(a[s] == 1)
		    {
		      w[i] = 1;
		      break;
		    }
		  s++;
		  continue;
		}

	      if(a[s] == 1)
		{
		  s++;
		  continue;
		}
	      else
		{
		  w[i] = 0;
		  break;
		}
	    }
	  else
	    {
	      if(G[s].size())
		s++;
	      else
		{
		  w[i] = 0;
		  break;
		}
	    }
	}
    }
  return w;
}

Compilation message

train.cpp: In function 'std::vector<int> who_wins(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |   for(int i = 0; i < u.size(); i ++)
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25436 KB Output is correct
2 Correct 14 ms 25692 KB Output is correct
3 Correct 13 ms 25488 KB Output is correct
4 Correct 14 ms 25692 KB Output is correct
5 Correct 13 ms 25696 KB Output is correct
6 Correct 14 ms 25688 KB Output is correct
7 Correct 13 ms 25700 KB Output is correct
8 Correct 17 ms 25692 KB Output is correct
9 Correct 13 ms 25688 KB Output is correct
10 Correct 15 ms 25692 KB Output is correct
11 Correct 16 ms 25436 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 25688 KB Output is correct
2 Correct 32 ms 25948 KB Output is correct
3 Correct 31 ms 26080 KB Output is correct
4 Incorrect 37 ms 25948 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
5 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 754 ms 26080 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 25944 KB 3rd lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25436 KB Output is correct
2 Correct 14 ms 25692 KB Output is correct
3 Correct 13 ms 25488 KB Output is correct
4 Correct 14 ms 25692 KB Output is correct
5 Correct 13 ms 25696 KB Output is correct
6 Correct 14 ms 25688 KB Output is correct
7 Correct 13 ms 25700 KB Output is correct
8 Correct 17 ms 25692 KB Output is correct
9 Correct 13 ms 25688 KB Output is correct
10 Correct 15 ms 25692 KB Output is correct
11 Correct 16 ms 25436 KB Output is correct
12 Incorrect 1 ms 2396 KB 3rd lines differ - on the 2nd token, expected: '1', found: '0'
13 Halted 0 ms 0 KB -