Submission #68167

#	Time	Username	Problem	Language	Result	Execution time	Memory
68167		mirbek01	Toy Train (IOI17_train)	C++17	22 / 100	1107 ms	3752 KiB

train

#include "train.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 2;

int n, m, used[N], vr;
vector <int> g[N], G[N], r, res;
bool fl;

void dfs(int v){
      used[v] = 1;
      for(int to : g[v]){
            if(used[to] == 1){
                  if(to == vr) fl = 1;
            } else if(!used[to])
                  dfs(to);
      }
      used[v] = 2;
}

void dfs1(int v){
      used[v] = 1;
      for(int to : g[v]){
            if(r[to]) continue;
            if(used[to] == 1){
                  fl = 1;
            } else if(!used[to])
                  dfs1(to);
      }
      used[v] = 2;
}

void bfs(int s){
      memset(used, 0, sizeof(used));
      queue <int> q;
      q.push(s);
      used[s] = 1;
      while(!q.empty()){
            int v = q.front();
            res[v] = 1;
            q.pop();
            for(int to : G[v]){
                  if(used[to]) continue;
                  used[to] = 1;
                  q.push(to);
            }
      }
}

vector<int> who_wins(vector<int> a, vector<int> R, vector<int> u, vector<int> v) {
	n = (int)(a.size());
	m = (int)(u.size());
	r = R;
      res.resize(n);
      int sum = 0;
      for(int i = 0; i < n; i ++){
            sum += a[i];
      }

      for(int i = 0; i < m; i ++){
            g[u[i]].push_back(v[i]);
            G[v[i]].push_back(u[i]);
      }

      if(sum == n){
            for(int s = 0; s < n; s ++){
                  if(r[s]){
                        memset(used, 0, sizeof(used));
                        fl = 0;
                        vr = s;
                        dfs(s);
                        if(fl){
                              bfs(s);
                        }
                  }
            }
      }

      if(!sum){
            for(int s = 0; s < n; s ++){
                  if(!r[s]){
                        memset(used, 0, sizeof(used));
                        fl = 0;
                        dfs1(s);
                        if(fl){
                              bfs(s);
                        }
                  }
            }
            for(int s = 0; s < n; s ++)
                  res[s] = 1 - res[s];
      }

	return res;
}

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