oj.uz

Submission #220379

# Submission time Handle Problem Language Result Execution time Memory
220379 2020-04-07T19:05:29 Z WLZ Stray Cat (JOI20_stray) C++14
15 / 100
 77 ms 16960 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
  const vector<int> period = {0, 1, 0, 0, 1, 1};

  struct edge {
    int from, to, idx;
  };
  vector< vector<edge> > g;

  vector<int> solve1234(int N, int M, vector<int> U, vector<int> V) {
    queue<int> q;
    q.push(0);
    vector<int> dist(N, -1), ans(M, -1);
    dist[0] = 0;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (auto& e : g[u]) {
        if (dist[e.to] == -1) {
          dist[e.to] = dist[u] + 1;
          q.push(e.to);
        }
      }
    }
    for (int i = 0; i < M; i++) {
      ans[i] = min(dist[U[i]], dist[V[i]]) % 3;
    }
    return ans;
  }

  vector<int> solve567(int N, int M, vector<int> U, vector<int> V) {
    vector<int> prev(N, 1), was(N, 0), len(N, 0), ans(M, -1);
    queue<int> q; q.push(0);
    was[0] = 1;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      if ((int) g[u].size() == 2) {
        if (len[u] == 0) {
          if (prev[u] == 0) {
            len[u] = 1;
          }
        }
      }
      for (auto& e : g[u]) {
        if (!was[e.to]) {
          if ((int) g[u].size() == 2 || u == 0) {
            len[e.to] = len[u] + 1;
            ans[e.idx] = period[len[u] % 6];
          } else {
            ans[e.idx] = !prev[u];
          }
          q.push(e.to);
          was[e.to] = 1;
          prev[e.to] = ans[e.idx];
        }
      }
    }
    return ans;
  }
}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
  g.resize(N);
  for (int i = 0; i < M; i++) {
    g[U[i]].push_back({U[i], V[i], i});
    g[V[i]].push_back({V[i], U[i], i});
  }
  if (A >= 3) {
    return solve1234(N, M, U, V);
  } else {
    return solve567(N, M, U, V);
  }
}

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
  const vector<int> period = {0, 1, 0, 0, 1, 1};
  vector<int> cur;

  int A, B, start = 1, rev = 0, last;
}

void Init(int A, int B) {
  ::A = A; ::B = B;
}

int Move(vector<int> y) {
  if (A >= 3) {
    for (int i = 0; i < 3; i++) {
      if (y[i] > 0 && y[(i + 1) % 3] > 0) {
        return i;
      }
    }
    for (int i = 0; i < 3; i++) {
      if (y[i] > 0) {
        return i;
      }
    }
  } else {
    if (rev) {
      int tmp = cur.back();
      cur.pop_back();
      if (cur.empty()) {
        rev = 0;
      }
      return (last = tmp);
    }
    if (y[0] > 1 && y[1] > 0) {
      start = 0;
      return (last = 1);
    }
    if (y[0] > 1 && y[1] > 0) {
      start = 0;
      return (last = 0);
    }
    if (y[0] == 0 && y[1] == 0) {
      start = 0;
      return (last = -1);
    }
    if (start) {
      if (y[0] > 0 && y[1] > 0 && !cur.empty()) {
        start = 0;
        return (last = !cur.back());
      }
      if (cur.empty()) {
        if (y[0] == 1 && y[1] == 0) {
          start = 0;
          return 0;
        }
        if (y[1] == 1 && y[0] == 0) {
          start = 0;
          return 1;
        }
      }
      for (int i = 0; i < 2; i++) {
        if (y[i] > 0) {
          if (cur.empty()) {
            if (y[i] > 1) {
              cur.push_back(i);
            } else {
              cur.push_back(!i);
            }
          }
          cur.push_back(i);
          break;
        }
      }
      if ((int) cur.size() == 5) {
        start = 0;
        for (auto& x : cur) {
          cout << x << ' ';
        }
        cout << endl;
        for (int i = 0; i < 6; i++) {
          int match = 1;
          for (int j = 0; j < 5; j++) {
            if (period[(i + j) % 6] != cur[j]) {
              match = 0;
              break;
            }
          }
          if (match) {
            rev = 1;
            cur.pop_back();
            cur.pop_back();
            return -1;
          }
        }
      }
      if (!rev) {
        return (last = cur.back());
      }
    } else {
      if (y[0] == 1 && y[1] == 1) {
        last = !last;
        return last;
      }
      if (y[0] > 0) {
        return (last = 0);
      }
      return (last = 1);
    }
  }
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 15884 KB Output is correct
2 Correct 8 ms 780 KB Output is correct
3 Correct 48 ms 15236 KB Output is correct
4 Correct 66 ms 16960 KB Output is correct
5 Correct 66 ms 16884 KB Output is correct
6 Correct 55 ms 15612 KB Output is correct
7 Correct 54 ms 15756 KB Output is correct
8 Correct 63 ms 16464 KB Output is correct
9 Correct 66 ms 16592 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 15884 KB Output is correct
2 Correct 8 ms 780 KB Output is correct
3 Correct 48 ms 15236 KB Output is correct
4 Correct 66 ms 16960 KB Output is correct
5 Correct 66 ms 16884 KB Output is correct
6 Correct 55 ms 15612 KB Output is correct
7 Correct 54 ms 15756 KB Output is correct
8 Correct 63 ms 16464 KB Output is correct
9 Correct 66 ms 16592 KB Output is correct
10 Correct 50 ms 13916 KB Output is correct
11 Correct 51 ms 13912 KB Output is correct
12 Correct 49 ms 13828 KB Output is correct
13 Correct 49 ms 13764 KB Output is correct
14 Correct 51 ms 14060 KB Output is correct
15 Correct 56 ms 14452 KB Output is correct
16 Correct 60 ms 16456 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13436 KB Output is correct
2 Correct 9 ms 780 KB Output is correct
3 Correct 45 ms 13140 KB Output is correct
4 Correct 77 ms 14916 KB Output is correct
5 Correct 67 ms 14756 KB Output is correct
6 Correct 50 ms 13668 KB Output is correct
7 Correct 53 ms 13668 KB Output is correct
8 Correct 60 ms 14196 KB Output is correct
9 Correct 60 ms 14084 KB Output is correct
10 Correct 57 ms 14012 KB Output is correct
11 Correct 55 ms 13948 KB Output is correct
12 Correct 61 ms 14144 KB Output is correct
13 Correct 56 ms 14028 KB Output is correct
14 Correct 60 ms 14276 KB Output is correct
15 Correct 60 ms 14284 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13436 KB Output is correct
2 Correct 9 ms 780 KB Output is correct
3 Correct 45 ms 13140 KB Output is correct
4 Correct 77 ms 14916 KB Output is correct
5 Correct 67 ms 14756 KB Output is correct
6 Correct 50 ms 13668 KB Output is correct
7 Correct 53 ms 13668 KB Output is correct
8 Correct 60 ms 14196 KB Output is correct
9 Correct 60 ms 14084 KB Output is correct
10 Correct 57 ms 14012 KB Output is correct
11 Correct 55 ms 13948 KB Output is correct
12 Correct 61 ms 14144 KB Output is correct
13 Correct 56 ms 14028 KB Output is correct
14 Correct 60 ms 14276 KB Output is correct
15 Correct 60 ms 14284 KB Output is correct
16 Correct 46 ms 11932 KB Output is correct
17 Correct 47 ms 11776 KB Output is correct
18 Correct 49 ms 12140 KB Output is correct
19 Correct 49 ms 12000 KB Output is correct
20 Correct 54 ms 12656 KB Output is correct
21 Correct 54 ms 12572 KB Output is correct
22 Correct 56 ms 14272 KB Output is correct
23 Correct 50 ms 12144 KB Output is correct
24 Correct 50 ms 12140 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 908 KB Output is correct
2 Correct 10 ms 788 KB Output is correct
3 Correct 10 ms 1116 KB Output is correct
4 Correct 10 ms 1036 KB Output is correct
5 Correct 11 ms 1120 KB Output is correct
6 Correct 10 ms 1036 KB Output is correct
7 Correct 11 ms 1120 KB Output is correct
8 Incorrect 10 ms 1132 KB Your program terminated abnormally, or printed anything to standard output.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11956 KB Output is correct
2 Correct 55 ms 12712 KB Output is correct
3 Correct 9 ms 780 KB Output is correct
4 Correct 45 ms 11880 KB Output is correct
5 Correct 61 ms 12848 KB Output is correct
6 Incorrect 66 ms 13096 KB Your program terminated abnormally, or printed anything to standard output.
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 11900 KB Your program terminated abnormally, or printed anything to standard output.
2 Halted 0 ms 0 KB -