Submission #146518

#	Time	Username	Problem	Language	Result	Execution time	Memory
146518		neki	Toy Train (IOI17_train)	C++14	100 / 100	667 ms	2552 KiB

train

#include <bits/stdc++.h>
#include "train.h"
#define loop(i, a, b) for(int i=a;i<b;i++)
#define maxn 20100
using namespace std;
vector<int> ba[maxn], fo[maxn], ans, req, po;

void dfs(int u){loop(i, 0, ba[u].size()){ int v=ba[u][i];req[v]--; if(!req[v] && !po[v]) dfs(v);}};

vector<int> who_wins(vector<int> A, vector<int> C, vector<int> U, vector<int> V){
  int n=A.size(), m=U.size();po.resize(n);loop(i, 0, n) po[i]=C[i];
  loop(i, 0, m) ba[V[i]].push_back(U[i]), fo[U[i]].push_back(V[i]);
  ans.resize(n, 1), req.resize(n);
  bool cn=1;
  while(cn){
    cn=0;
    loop(i, 0, n) req[i]=(A[i])? 1:fo[i].size();
    loop(i, 0, n) if(po[i]&&ans[i]) dfs(i);
    loop(i, 0, n) if(ans[i]&&po[i]&&(req[i]>0)) ans[i]=0, cn=1;
  }
  loop(i, 0, n) ans[i]&=req[i]<1;
  return ans;
}

Compilation message (stderr)

train.cpp: In function 'void dfs(int)':
train.cpp:3:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define loop(i, a, b) for(int i=a;i<b;i++)
train.cpp:8:22:
 void dfs(int u){loop(i, 0, ba[u].size()){ int v=ba[u][i];req[v]--; if(!req[v] && !po[v]) dfs(v);}};
                      ~~~~~~~~~~~~~~~~~~
train.cpp:8:17: note: in expansion of macro 'loop'
 void dfs(int u){loop(i, 0, ba[u].size()){ int v=ba[u][i];req[v]--; if(!req[v] && !po[v]) dfs(v);}};
                 ^~~~

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