Submission #68177

#	Time	Username	Problem	Language	Result	Execution time	Memory
68177		mirbek01	Toy Train (IOI17_train)	C++17	22 / 100	1280 ms	3256 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];
      }

      map < pair <int, int>, int > mp;

      for(int i = 0; i < m; i ++){
            mp[{u[i], v[i]}] = 1;
            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);
                        }
                  }
            }
      } else 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];
      } else {
            for(int s = n - 1; s >= 0; s --){
                  if(s == n - 1){
                        if(r[s])
                              res[s] = 1;
                        else
                              res[s] = 0;
                  } else {
                        if(r[s]){
                              if(a[s])
                                    res[s] = 1;
                              else
                                    res[s] = res[s + 1];
                        } else {
                              if(a[s])
                                    res[s] = res[s + 1];
                              else
                                    res[s] = 0;
                        }
                  }
            }
      }

	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