Submission #149882

#	Time	Username	Problem	Language	Result	Execution time	Memory
149882		등수만큼 신재웅 생일빵 때림 (10대) (#200)	Bulb Game (FXCUP4_bulb)	C++17	100 / 100	102 ms	23660 KiB

bulb

#include "bulb.h"
#include "bits/stdc++.h"
using namespace std;

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[";
  for (auto x : V) os << x << ", ";
  return os << "]";
}
template <typename... Args>
void dbg(Args... args) {
  ((cerr << args << " "), ...);
  cerr << "\n";
}
void dfs(int c, vector<int> &L, vector<int> &R, vector<int> &cur, vector<int> &change) {
  if (L[c] == -1 || L[c] == -2) {
    cur[c] = -L[c];
  } else {
    dfs(L[c], L, R, cur, change);
    cur[c] = cur[L[c]];
  }
  if (R[c] == -1 || R[c] == -2) {
    change[c] = -R[c];
  } else {
    dfs(R[c], L, R, cur, change);
    change[c] = cur[R[c]];
  }
}
int FindWinner(int T, std::vector<int> L, std::vector<int> R) {
  int N = L.size();

  vector<int> cur(N, 0), change(N, 0);  // 1: R, 2: B
  dfs(0, L, R, cur, change);
  if (N == 1) {
    if (cur[0] == 1)
      return 1;
    else
      return 0;
  }
  // dbg(cur, change);
  if (cur[0] == 2) return 0;

  vector<int> idx;
  int pv = 0;
  while (pv >= 0) {
    idx.push_back(pv);
    pv = L[pv];
  }
  int i = 0;
  for (; i < idx.size(); i++) {
    if (change[idx[i]] == 2) break;
  }
  if (i == idx.size()) {
    int cnt = 0;
    for (int j = 0; j < i; j++) {
      cnt++;
      int pv = R[idx[j]];
      if (pv < 0) return 1;
      while (pv >= 0) {
        cnt++;
        pv = L[pv];
      }
    }
    if (cnt < N) return 1;

    for (int j = 0; j < i; j++) {
      int pv = R[idx[j]];
      if (pv == -1) return 1;
      while (pv >= 0) {
        if (change[pv] == 1) return 1;
        cnt++;
        pv = L[pv];
      }
    }
    return 0;
  }

  for (int j = 0; j < i; j++) {
    int pv = R[idx[j]];
    int flag = true;
    while (pv >= 0) {
      if (change[pv] == 2) flag = false;
      pv = L[pv];
    }
    if (flag) return 1;
  }
  int cnt = 0;
  for (int j; j < i; j++) {
    cnt++;
    int pv = R[idx[j]];
    while (pv >= 0) {
      cnt++;
      pv = L[pv];
    }
  }
  pv = R[idx[i]];
  while (pv >= 0) {
    cnt++;
    pv = L[pv];
  }
  if (cnt == N) {
    pv = R[idx[i]];
    while (pv >= 0) {
      if (change[pv] == 2) return 0;
      pv = L[pv];
    }
    return 1;
  }
  return 0;
}

Compilation message (stderr)

bulb.cpp: In function 'int FindWinner(int, std::vector<int>, std::vector<int>)':
bulb.cpp:55:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; i < idx.size(); i++) {
          ~~^~~~~~~~~~~~
bulb.cpp:58:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == idx.size()) {
       ~~^~~~~~~~~~~~~
bulb.cpp:93:12: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   for (int j; j < i; j++) {
            ^

• Subtask 1: 11 / 11
• Subtask 2: 25 / 25
• Subtask 3: 64 / 64