oj.uz

Submission #674324

# Submission time Handle Problem Language Result Execution time Memory
674324 2022-12-23T17:20:24 Z null_awe Stray Cat (JOI20_stray) C++14
15 / 100
 45 ms 16592 KB 
#include "Anthony.h"
#include <iostream>
#include <set>
#include <vector>
#include <queue>
#include <assert.h>
using namespace std;

#define pii pair<int, int>

vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v) {
  vector<vector<pii>> adj(n);
  for (int i = 0; i < m; ++i) adj[u[i]].push_back({v[i], i}), adj[v[i]].push_back({u[i], i});
  if (a == 2) {
    vector<int> color(m, -1), dist(n, -1), lp(n), llp(n);
    for (int i = 0; i < n; ++i) lp[i] = i, llp[i] = i;
    queue<int> q; q.push(0), dist[0] = 0;
    set<int> heads;
    while (q.size()) {
      int v = q.front(); q.pop();
      int label = dist[v] % 2;
      for (const auto& [u, i] : adj[v]) {
        if (color[i] >= 0) {
          if (adj[v].size() == 2) {
            lp[v] = lp[u];
            if (lp[u] == u) heads.insert(v);
            else llp[v] = llp[u];
          }
          continue;
        }
        color[i] = label;
        q.push(u), dist[u] = dist[v] + 1;
      }
    }
    for (int i = 0; i < m; ++i) {
      //cout << u[i] << ' ' << v[i] << ' ' << color[i] << endl;
    }
    vector<int> pat = {1, 1, 0, 0, 1, 0};
    vector<int> shifts(n);
    for (int p : heads) {
      int cur = p;
      while (true) {
        bool can = false;
        for (const auto& [u, i] : adj[cur]) {
          if (dist[u] > dist[cur] && adj[u].size() == 2) can = true, cur = u;
        }
        if (!can) break;
      }
      int v1 = dist[lp[p]] % 2, v2 = dist[cur] % 2;
      int dd = dist[cur] - dist[lp[p]];
      int shift = 0;
      if (dd % 6 == 0) shift = v1 ? 0 : 2;
      else if (dd % 6 == 1) shift = v1 ? 1 : 3;
      else if (dd % 6 == 2) shift = v1 ? 4 : 3;
      else if (dd % 6 == 3) shift = v1 ? 0 : 3;
      else if (dd % 6 == 4) shift = v1 ? 0 : 5;
      else shift = v1 ? 0 : 5;
      shifts[p] = shift;
    }
    for (int v = 1; v < n; ++v) {
      if (adj[v].size() != 2) continue;
      int p = lp[v];
      int shift = shifts[llp[v]];
      for (const auto& [u, i] : adj[v]) {
        if (dist[u] > dist[v]) {
          color[i] = pat[(dist[v] - dist[p] + shift) % 6];
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      //cout << u[i] << ' ' << v[i] << ' ' << color[i] << endl;
    }
    return color;
  }
  vector<int> color(m, -1), dist(n, -1);
  queue<int> q; q.push(0), dist[0] = 0;
  while (q.size()) {
    int v = q.front(); q.pop();
    int label = dist[v] % 3;
    for (const auto& [u, i] : adj[v]) {
      if (color[i] >= 0) continue;
      color[i] = label;
      if (dist[u] < 0) q.push(u), dist[u] = dist[v] + 1;
    }
  }
  for (int num : color) assert(num >= 0 && num < 3);
  return color;
}


#include "Catherine.h"
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

int a;

void Init(int _a, int _b) {
  a = _a;
}

int prv = -1;
bool start = false;
vector<int> seen;

bool forwards() {
  assert(seen.size() == 5);
  vector<int> f1 = {0, 1, 0, 0, 1};
  vector<int> f2 = {1, 0, 0, 1, 1};
  vector<int> f3 = {0, 0, 1, 1, 0};
  vector<int> f4 = {0, 1, 1, 0, 1};
  vector<int> f5 = {1, 1, 0, 1, 0};
  vector<int> f6 = {1, 0, 1, 0, 0};
  return seen == f1 || seen == f2 || seen == f3 || seen == f4 || seen == f5 || seen == f6;
}

int Move(vector<int> y) {
  vector<int> copy = y;
  y.clear();
  for (int i = 0; i < copy.size(); ++i)
    for (int j = 0; j < copy[i]; ++j) y.push_back(i);
  if (a == 2) {
    if (start) {
      if (y.size() == 1) {
        return prv = y[0];
      }
      for (int i = 0; i < y.size(); ++i) {
        if (y[i] != prv) {
          return prv = y[i];
        }
      }
      // Shouldn't ever happen:
      //cout << copy[0] << ' ' << copy[1] << endl;
      assert(0);
      return 0;
    } else {
      if (y.size() > 1) {
        int sum = 0;
        for (int num : y) sum += num;
        if (sum == 0 || sum == y.size()) {
          start = true;
          return -1;
        }
        if (prv == -1 && y.size() == 2) {
          seen.push_back(y[0]), seen.push_back(y[1]);
          return prv = y[1];
        }
        if (prv == -1) {
          int find = sum == 1;
          for (int i = 0; i < y.size(); ++i) {
            if (y[i] == find) {
              start = true;
              return prv = y[i];
            }
          }
          // Shouldn't ever happen:
          assert(0);
          return 0;
        }
        for (int i = 0; i < y.size(); ++i) {
          if (y[i] != prv) {
            start = true;
            return prv = y[i];
          }
        }
        // Shouldn't ever happen:
        assert(0);
        return 0;
      } else {
        if (y.size() == 0) {
          start = true;
          return -1;
        }
        seen.push_back(y[0]);
        if (seen.size() < 5) {
          return prv = y[0];
        }
        start = true;
        if (forwards()) {
          return prv = y[0];
        }
        return -1;
      }
      // Shouldn't ever happen:
      assert(0);
      return 0;
    }
  }
  vector<int> count(3);
  for (int num : y) ++count[num];
  if (max(count[0], max(count[1], count[2])) == y.size()) return y[0];
  return !count[0] ? 1 : (!count[1] ? 2 : 0);
}

Compilation message

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:22:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |       for (const auto& [u, i] : adj[v]) {
      |                        ^
Anthony.cpp:44:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         for (const auto& [u, i] : adj[cur]) {
      |                          ^
Anthony.cpp:49:33: warning: unused variable 'v2' [-Wunused-variable]
   49 |       int v1 = dist[lp[p]] % 2, v2 = dist[cur] % 2;
      |                                 ^~
Anthony.cpp:64:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |       for (const auto& [u, i] : adj[v]) {
      |                        ^
Anthony.cpp:80:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for (const auto& [u, i] : adj[v]) {
      |                      ^

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for (int i = 0; i < copy.size(); ++i)
      |                   ~~^~~~~~~~~~~~~
Catherine.cpp:38:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |       for (int i = 0; i < y.size(); ++i) {
      |                       ~~^~~~~~~~~~
Catherine.cpp:51:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if (sum == 0 || sum == y.size()) {
      |                         ~~~~^~~~~~~~~~~
Catherine.cpp:61:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |           for (int i = 0; i < y.size(); ++i) {
      |                           ~~^~~~~~~~~~
Catherine.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < y.size(); ++i) {
      |                         ~~^~~~~~~~~~
Catherine.cpp:102:46: warning: comparison of integer expressions of different signedness: 'const int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   if (max(count[0], max(count[1], count[2])) == y.size()) return y[0];
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14992 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 28 ms 14836 KB Output is correct
4 Correct 45 ms 16592 KB Output is correct
5 Correct 44 ms 16580 KB Output is correct
6 Correct 34 ms 15300 KB Output is correct
7 Correct 35 ms 15272 KB Output is correct
8 Correct 40 ms 15984 KB Output is correct
9 Correct 40 ms 16012 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14992 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 28 ms 14836 KB Output is correct
4 Correct 45 ms 16592 KB Output is correct
5 Correct 44 ms 16580 KB Output is correct
6 Correct 34 ms 15300 KB Output is correct
7 Correct 35 ms 15272 KB Output is correct
8 Correct 40 ms 15984 KB Output is correct
9 Correct 40 ms 16012 KB Output is correct
10 Correct 31 ms 13288 KB Output is correct
11 Correct 31 ms 13340 KB Output is correct
12 Correct 32 ms 13360 KB Output is correct
13 Correct 34 ms 13356 KB Output is correct
14 Correct 33 ms 13604 KB Output is correct
15 Correct 37 ms 14068 KB Output is correct
16 Correct 41 ms 16044 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12640 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 27 ms 12632 KB Output is correct
4 Correct 41 ms 14316 KB Output is correct
5 Correct 43 ms 14288 KB Output is correct
6 Correct 33 ms 13100 KB Output is correct
7 Correct 34 ms 13132 KB Output is correct
8 Correct 38 ms 13708 KB Output is correct
9 Correct 39 ms 13780 KB Output is correct
10 Correct 36 ms 13548 KB Output is correct
11 Correct 36 ms 13404 KB Output is correct
12 Correct 37 ms 13536 KB Output is correct
13 Correct 39 ms 13440 KB Output is correct
14 Correct 39 ms 13696 KB Output is correct
15 Correct 39 ms 13736 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12640 KB Output is correct
2 Correct 0 ms 520 KB Output is correct
3 Correct 27 ms 12632 KB Output is correct
4 Correct 41 ms 14316 KB Output is correct
5 Correct 43 ms 14288 KB Output is correct
6 Correct 33 ms 13100 KB Output is correct
7 Correct 34 ms 13132 KB Output is correct
8 Correct 38 ms 13708 KB Output is correct
9 Correct 39 ms 13780 KB Output is correct
10 Correct 36 ms 13548 KB Output is correct
11 Correct 36 ms 13404 KB Output is correct
12 Correct 37 ms 13536 KB Output is correct
13 Correct 39 ms 13440 KB Output is correct
14 Correct 39 ms 13696 KB Output is correct
15 Correct 39 ms 13736 KB Output is correct
16 Correct 28 ms 11492 KB Output is correct
17 Correct 28 ms 11496 KB Output is correct
18 Correct 30 ms 11368 KB Output is correct
19 Correct 31 ms 11508 KB Output is correct
20 Correct 37 ms 12016 KB Output is correct
21 Correct 33 ms 11808 KB Output is correct
22 Correct 37 ms 13992 KB Output is correct
23 Correct 34 ms 11508 KB Output is correct
24 Correct 30 ms 11556 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 1 ms 520 KB Output is correct
3 Correct 2 ms 908 KB Output is correct
4 Correct 2 ms 900 KB Output is correct
5 Correct 2 ms 908 KB Output is correct
6 Correct 2 ms 900 KB Output is correct
7 Incorrect 2 ms 860 KB Wrong Answer [4]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11332 KB Output is correct
2 Correct 34 ms 12136 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 28 ms 11328 KB Output is correct
5 Correct 42 ms 12516 KB Output is correct
6 Incorrect 31 ms 11776 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11408 KB Output is correct
2 Correct 34 ms 11892 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 28 ms 11460 KB Output is correct
5 Correct 40 ms 12580 KB Output is correct
6 Incorrect 31 ms 11692 KB Wrong Answer [4]
7 Halted 0 ms 0 KB -