oj.uz

Submission #1061220

# Submission time Handle Problem Language Result Execution time Memory
1061220 2024-08-16T07:21:35 Z vjudge1 Toy Train (IOI17_train) C++17
0 / 100
 99 ms 25924 KB 
// #include "train.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 5000 + 10;
vector<int> G[N];
bool R[N], seen[N][N];
int n;

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

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

vector<int> Arezou()
{
  vector<int> w(n);
  for(int s = 0; s < n; s++)
    w[s] = dfs(s, s);
  return w;
}

vector<int> Borzou()
{
  vector<int> w(n);
  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 < 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 && r[s] && (G[s].size() == 1 || a[s] == 1))
	    {
	      w[i] = 1;
	      break;
	    }
	  
	  if(cycle && G[s].size() == 1)
	    break;
	  s++;
	}
    }
  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:43:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for(int i = 0; i < u.size(); i ++)
      |                  ~~^~~~~~~~~~
train.cpp:53:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   if(c == a.size())
      |      ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1116 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 Runtime error 5 ms 2140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 51.0

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