oj.uz

Submission #149865

# Submission time Handle Problem Language Result Execution time Memory
149865 2019-09-01T07:18:11 Z 등수만큼 신재웅 생일빵 때림 (10대)(#3628, kjp4155, GodTe, JWoong148) Bulb Game (FXCUP4_bulb) C++17
11 / 100
 3 ms 504 KB 
#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 = R[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 = R[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 = R[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 = R[pv];
    }
  }
  pv = R[idx[i]];
  while (pv >= 0) {
    cnt++;
    pv = R[pv];
  }
  if (cnt == N) {
    pv = R[idx[i]];
    while (pv >= 0) {
      if (change[pv] == 2) return 0;
      pv = R[pv];
    }
    return 1;
  }
  return 0;
}

Compilation message

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 316 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 316 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Incorrect 2 ms 376 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 316 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Incorrect 2 ms 376 KB Output isn't correct
18 Halted 0 ms 0 KB -