oj.uz

Submission #577519

# Submission time Handle Problem Language Result Execution time Memory
577519 2022-06-15T03:40:04 Z Kanon Toy Train (IOI17_train) C++14
100 / 100
 1186 ms 100084 KB 
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);


vector<int> who_wins(vector<int> owned, vector<int> z, vector<int> From, vector<int> To) {
  int n = owned.size();
  int m = To.size();
  vector<vector<int>> g(n);
  vector<vector<int>> Rev(n);
  for (int i = 0; i < m; i++) {
    g[From[i]].push_back(To[i]);
    Rev[To[i]].push_back(From[i]);
  }

  vector<int> ret(n, -1);

  {
    vector<int> was(n);
    vector<int> alive(n);
    function<void(int)> dfs = [&] (int v) {
      was[v] = 1;
      for (int i : g[v]) {
        if (alive[i] && !was[i]) {
          dfs(i);
        }
      }
    };

    auto winstate = [&](vector<int> keep, vector<int> nodes) {
      fill(alive.begin(), alive.end(), 0);
      for (int i : keep) {
        alive[i] = 1;
      }

      vector<vector<int>> r(n);
      for (int i = 0; i < n; i++) {
        if (!alive[i]) {
          continue;
        }
        dfs(i);
        r[i] = was;
        fill(was.begin(), was.end(), 0);
      }

      vector<bool> win(n);
      for (int i : nodes) {
        for (int j : g[i]) {
          if (alive[j] && r[j][i] == 1) {
            win[i] = true;
          }
        }
      }
      return win;
    };

    auto get_win = [&](vector<int> keep, vector<bool> &win) {
      while (true) {
        bool change = false;
        for (int i : keep) {
          if (win[i]) {
            continue;
          }
          for (int j : g[i]) {
            if (win[j]) {
              win[i] = true;
              change = true;
            }
          }
        }
        if (!change) {
          break;
        }
      }
    };

    for (int player = 0; player < 2; player++) {
      vector<int> keep;
      vector<int> nodes;

      for (int i = 0; i < n; i++) {
        if (owned[i] != player) {
          continue;
        }
        if (player == 1) {
          keep.push_back(i);
          if (z[i]) {
            nodes.push_back(i);
          }
        } else {
          if (!z[i]) {
            keep.push_back(i);
            nodes.push_back(i);
          }
        }
      }

      vector<bool> win = winstate(keep, nodes);

      if (player == 0) {
        keep.clear();
        for (int i = 0; i < n; i++) {
          if (owned[i] == player) {
            keep.push_back(i);
          }
        }
      }

      get_win(keep, win);
      for (int i = 0; i < n; i++) {
        if (win[i]) {
          assert(ret[i] != (player ^ 1));
          ret[i] = player;
        }
      }
    }
  }

  vector<bool> st(n);
  vector<int> deg(n);
  bool added;
  function<void(int, int)> dfs = [&](int v, int player) {
    for (int i : Rev[v]) {
      if (ret[i] != -1) {
        continue;
      }
      if (st[i]) {
        continue;
      }
      deg[i]--;
      if (owned[i] == player || (deg[i] == 0)) {
        st[i] = true;
        added = true;
        dfs(i, player);
      }
    }
  };

  auto spanning = [&](vector<bool> &base, int reachable, bool hard = false) {
    added = false;
    for (int i = 0; i < n; i++) {
      deg[i] = 0;
      if (ret[i] != -1) {
        continue;
      }
      for (int j : g[i]) {
        if (ret[j] == -1 || hard) {
          deg[i]++;
        }
      }
    }
    st = base;
    for (int i = 0; i < n; i++) {
      if (base[i]) {
        dfs(i, reachable);
      }
    }
    base = st;
    return added;
  };

  while (true) {
    vector<bool> bwin(n);
    vector<bool> awin(n);
    for (int i = 0; i < n; i++) {
      if (ret[i] == 0) {
        bwin[i] = true;
      }
      if (ret[i] == 1) {
        awin[i] = true;
      }
    }

    bool change = spanning(awin, 1, true) | spanning(bwin, 0, true);
    if (!change) {
      break;
    }
    for (int i = 0; i < n; i++) {
      if (bwin[i]) {
        ret[i] = 0;
      }
      if (awin[i]) {
        ret[i] = 1;
      }
      assert(!awin[i] || !bwin[i]);
    }
  }

  while (true) {
    vector<bool> removed(n);
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && z[i]) {
        removed[i] = true;
      }
    }
    spanning(removed, 1);
    removed = st;

    vector<bool> lost = removed;
    bool change = false;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1) {
        lost[i] = !lost[i];
        if (lost[i]) {
          change = true;
        }
      }
    }
    if (!change) {
      break;
    }
    spanning(lost, 0);
    lost = st;
    for (int i = 0; i < n; i++) {
      if (ret[i] == -1 && lost[i]) {
        ret[i] = 0;
      }
    }
  }

  for (int i = 0; i < n; i++) {
    if (ret[i] == -1) {
      ret[i] = 1;
    }
  }

  return ret;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 49800 KB Output is correct
2 Correct 41 ms 49616 KB Output is correct
3 Correct 40 ms 50528 KB Output is correct
4 Correct 41 ms 50448 KB Output is correct
5 Correct 37 ms 49684 KB Output is correct
6 Correct 40 ms 50560 KB Output is correct
7 Correct 27 ms 50128 KB Output is correct
8 Correct 57 ms 99192 KB Output is correct
9 Correct 41 ms 50768 KB Output is correct
10 Correct 36 ms 50948 KB Output is correct
11 Correct 62 ms 48964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 260 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 304 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 300 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 99952 KB Output is correct
2 Correct 561 ms 100040 KB Output is correct
3 Correct 641 ms 99868 KB Output is correct
4 Correct 1153 ms 100016 KB Output is correct
5 Correct 896 ms 99772 KB Output is correct
6 Correct 630 ms 99760 KB Output is correct
7 Correct 548 ms 99748 KB Output is correct
8 Correct 378 ms 99848 KB Output is correct
9 Correct 346 ms 99628 KB Output is correct
10 Correct 444 ms 99604 KB Output is correct
11 Correct 392 ms 99624 KB Output is correct
12 Correct 73 ms 99508 KB Output is correct
13 Correct 1186 ms 100084 KB Output is correct
14 Correct 1177 ms 99920 KB Output is correct
15 Correct 1137 ms 99812 KB Output is correct
16 Correct 1138 ms 99992 KB Output is correct
17 Correct 1156 ms 99944 KB Output is correct
18 Correct 764 ms 99620 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7392 KB Output is correct
2 Correct 167 ms 99372 KB Output is correct
3 Correct 223 ms 96676 KB Output is correct
4 Correct 64 ms 50764 KB Output is correct
5 Correct 404 ms 97620 KB Output is correct
6 Correct 328 ms 95964 KB Output is correct
7 Correct 314 ms 92236 KB Output is correct
8 Correct 165 ms 81176 KB Output is correct
9 Correct 10 ms 6540 KB Output is correct
10 Correct 18 ms 23868 KB Output is correct
11 Correct 11 ms 10504 KB Output is correct
12 Correct 19 ms 25664 KB Output is correct
13 Correct 636 ms 99788 KB Output is correct
14 Correct 378 ms 99620 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 522 ms 80484 KB Output is correct
2 Correct 898 ms 79264 KB Output is correct
3 Correct 309 ms 60536 KB Output is correct
4 Correct 290 ms 50644 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 48 ms 50632 KB Output is correct
7 Correct 31 ms 1516 KB Output is correct
8 Correct 32 ms 1496 KB Output is correct
9 Correct 32 ms 1548 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 43 ms 2212 KB Output is correct

Subtask #6
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 49800 KB Output is correct
2 Correct 41 ms 49616 KB Output is correct
3 Correct 40 ms 50528 KB Output is correct
4 Correct 41 ms 50448 KB Output is correct
5 Correct 37 ms 49684 KB Output is correct
6 Correct 40 ms 50560 KB Output is correct
7 Correct 27 ms 50128 KB Output is correct
8 Correct 57 ms 99192 KB Output is correct
9 Correct 41 ms 50768 KB Output is correct
10 Correct 36 ms 50948 KB Output is correct
11 Correct 62 ms 48964 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 292 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 1 ms 260 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 1 ms 304 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 300 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 402 ms 99952 KB Output is correct
33 Correct 561 ms 100040 KB Output is correct
34 Correct 641 ms 99868 KB Output is correct
35 Correct 1153 ms 100016 KB Output is correct
36 Correct 896 ms 99772 KB Output is correct
37 Correct 630 ms 99760 KB Output is correct
38 Correct 548 ms 99748 KB Output is correct
39 Correct 378 ms 99848 KB Output is correct
40 Correct 346 ms 99628 KB Output is correct
41 Correct 444 ms 99604 KB Output is correct
42 Correct 392 ms 99624 KB Output is correct
43 Correct 73 ms 99508 KB Output is correct
44 Correct 1186 ms 100084 KB Output is correct
45 Correct 1177 ms 99920 KB Output is correct
46 Correct 1137 ms 99812 KB Output is correct
47 Correct 1138 ms 99992 KB Output is correct
48 Correct 1156 ms 99944 KB Output is correct
49 Correct 764 ms 99620 KB Output is correct
50 Correct 10 ms 7392 KB Output is correct
51 Correct 167 ms 99372 KB Output is correct
52 Correct 223 ms 96676 KB Output is correct
53 Correct 64 ms 50764 KB Output is correct
54 Correct 404 ms 97620 KB Output is correct
55 Correct 328 ms 95964 KB Output is correct
56 Correct 314 ms 92236 KB Output is correct
57 Correct 165 ms 81176 KB Output is correct
58 Correct 10 ms 6540 KB Output is correct
59 Correct 18 ms 23868 KB Output is correct
60 Correct 11 ms 10504 KB Output is correct
61 Correct 19 ms 25664 KB Output is correct
62 Correct 636 ms 99788 KB Output is correct
63 Correct 378 ms 99620 KB Output is correct
64 Correct 522 ms 80484 KB Output is correct
65 Correct 898 ms 79264 KB Output is correct
66 Correct 309 ms 60536 KB Output is correct
67 Correct 290 ms 50644 KB Output is correct
68 Correct 1 ms 340 KB Output is correct
69 Correct 48 ms 50632 KB Output is correct
70 Correct 31 ms 1516 KB Output is correct
71 Correct 32 ms 1496 KB Output is correct
72 Correct 32 ms 1548 KB Output is correct
73 Correct 3 ms 468 KB Output is correct
74 Correct 43 ms 2212 KB Output is correct
75 Correct 272 ms 41032 KB Output is correct
76 Correct 387 ms 41076 KB Output is correct
77 Correct 438 ms 60448 KB Output is correct
78 Correct 462 ms 60492 KB Output is correct
79 Correct 443 ms 60484 KB Output is correct
80 Correct 295 ms 49772 KB Output is correct
81 Correct 154 ms 51688 KB Output is correct
82 Correct 93 ms 68428 KB Output is correct
83 Correct 774 ms 89736 KB Output is correct
84 Correct 676 ms 89124 KB Output is correct
85 Correct 131 ms 80792 KB Output is correct
86 Correct 684 ms 94924 KB Output is correct
87 Correct 227 ms 93500 KB Output is correct
88 Correct 124 ms 50536 KB Output is correct
89 Correct 124 ms 78524 KB Output is correct
90 Correct 129 ms 50356 KB Output is correct
91 Correct 527 ms 90136 KB Output is correct
92 Correct 458 ms 78120 KB Output is correct
93 Correct 163 ms 80204 KB Output is correct
94 Correct 148 ms 51096 KB Output is correct
95 Correct 180 ms 51292 KB Output is correct
96 Correct 164 ms 80212 KB Output is correct
97 Correct 899 ms 93056 KB Output is correct
98 Correct 812 ms 69424 KB Output is correct
99 Correct 861 ms 75124 KB Output is correct
100 Correct 783 ms 99536 KB Output is correct