oj.uz

Submission #33245

# Submission time Handle Problem Language Result Execution time Memory
33245 2017-10-23T04:36:10 Z model_code Toy Train (IOI17_train) C++11
0 / 100
 9 ms 3268 KB 
#include "train.h"
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxn=5000;
bool mark[maxn],col[maxn][2];
vector<int> vec,ans,r,arezou,G[maxn],G1[maxn],topo;
int cnt,n,m,t[maxn],mol[maxn],deg[maxn];

bool good(int v)
{
  if(ans[v]==0) return false;
  return (arezou[v]==0 || deg[v]==G[v].size());
}

bool ok(int v)
{
  if(mark[v]) return false;
  return (r[v]==0 && ((arezou[v] &&  col[v][1]==0)||(arezou[v]==0 && col[v][0]==1)));
}

void dfs1(int v)
{
  mark[v]=true;
  mol[v]=cnt;
  t[cnt]++;
  for(int i=0;i<G1[v].size();i++)
    {
      int u=G1[v][i];
      if(ok(u))
	dfs1(u);
    }
}

void dfs(int v)
{
  mark[v]=true;
  for(int i=0;i<G[v].size();i++)
    {
      int u=G[v][i];
      if(ok(u))
	dfs(u);
    }
  topo.push_back(v);
}

void bfs()
{
  while(vec.size())
    {
      int v=vec.back();
      vec.pop_back();
      for(int i=0;i<G1[v].size();i++)
	{
	  int u=G1[v][i];
	  deg[u]++;
	  if(good(u)) vec.push_back(u),ans[u]=0;
	}
    }
}

vector<int> who_wins(vector<int> a, vector<int> R, vector<int> from, vector<int> to)
{
  arezou=a;
  r=R;
  n=a.size(),m=from.size();
  for(int i=0;i<n;i++) ans.push_back(1);
  for(int i=0;i<m;i++)
    {
      G[from[i]].push_back(to[i]);
      G1[to[i]].push_back(from[i]);
      col[from[i]][r[to[i]]]=true;
    }
  for(int i=0;i<n;i++)
    if(ok(i))
      dfs(i);
  memset(mark,false,sizeof mark);
  for(int i=topo.size()-1;i>-1;i--)
    {
      int v=topo[i];
      if(ok(v)){
	cnt++;
	dfs1(v);
      }
    }
  for(int i=0;i<n;i++) if(t[mol[i]]>1) vec.push_back(i),ans[i]=0;
  bfs();
  return ans;
}

Compilation message

train.cpp: In function 'bool good(int)':
train.cpp:15:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   return (arezou[v]==0 || deg[v]==G[v].size());
                                 ^
train.cpp: In function 'void dfs1(int)':
train.cpp:29:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<G1[v].size();i++)
                ^
train.cpp: In function 'void dfs(int)':
train.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<G[v].size();i++)
                ^
train.cpp: In function 'void bfs()':
train.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<G1[v].size();i++)
                    ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2920 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 Incorrect 0 ms 2240 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3256 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 6 ms 2996 KB 3rd lines differ - on the 696th token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3268 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 Incorrect 3 ms 2920 KB 3rd lines differ - on the 1st token, expected: '0', found: '1'
2 Halted 0 ms 0 KB -