oj.uz

Submission #974075

# Submission time Handle Problem Language Result Execution time Memory
974075 2024-05-02T18:02:41 Z Ooops_sorry Stray Cat (JOI20_stray) C++14
15 / 100
 42 ms 16516 KB 
#ifndef LOCAL
  #include "Anthony.h"
#endif 
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
 
using namespace std;
 
#define ull unsigned long long
#define pb push_back
#define ll long long
#define all(a) a.begin(), a.end()
#define ld long double 

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 2e4 + 10;
vector<pair<int, int>> g[N];

vector<int> res;

string s = "100110100110", rev_s = "011001011001";

void dfs(int v, int p, int pos) {
  if (v == 0) {
    for (auto [u, i] : g[v]) {
      res[i] = 1;
      dfs(u, v, 1);
    } 
  } else {
    int last = s[pos + 5] - '0';
    if (g[v].size() >= 3) {
      for (auto [u, i] : g[v]) {
        if (u != p) {
          res[i] = last ^ 1;
          dfs(u, v, last ^ 1);
        }
      }
    } else {
      for (auto [u, i] : g[v]) {
        if (u != p) {
          res[i] = s[pos] - '0';
          dfs(u, v, (pos + 1) % 6);
        }
      }
    }
  }
}

vector<int> Mark(int n, int m, int a, int b, vector<int> u, vector<int> v) {
  for (int i = 0; i < m; i++) {
    g[u[i]].pb({v[i], i});
    g[v[i]].pb({u[i], i});
  }
  if (a >= 3) {
    vector<int> d(n, -1);
    d[0] = 0;
    deque<int> q{0};
    while (q.size() > 0) {
      int v = q.front();
      q.pop_front();
      for (auto [u, i] : g[v]) {
        if (d[u] == -1) {
          d[u] = d[v] + 1;
          q.pb(u);
        }
      }
    }
    vector<int> ans(m, -1);
    for (int v = 0; v < n; v++) {
      for (auto [u, i] : g[v]) {
        if (d[u] == d[v]) {
          ans[i] = d[u] % 3;
        } else {
          ans[i] = min(d[u], d[v]) % 3;
        }
      }
    }
    return ans;
  } else {
    res.resize(m, -1);
    dfs(0, -1, -1);
    return res;
  }
}
#ifndef LOCAL
  #include "Catherine.h"
#endif 
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<map>
#include<random>
#include<time.h>
#include<cassert>
#include<chrono>
#include<set>
#include<unordered_set>
#include<array>
 
using namespace std;
 
#define ull unsigned long long
#define pb push_back
#define ll long long
#define all(a) a.begin(), a.end()
#define ld long double 

mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int A, B;

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

string kek = "";
bool top = 0;
int last = -1;

string s = "100110100110", rev_s = "011001011001";

bool in(string s, string t) {
  for (int i = 0; i + t.size() <= s.size(); i++) {
    if (s.substr(i, (int)t.size()) == t) {
      return 1;
    }
  }
  return 0;
}

int Move(std::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 {
    vector<int> y_new = y;
    if (last != -1) {
      y_new[last]++;
    }
    if (y_new[0] + y_new[1] > 2) {
      if (y_new[0] == 1) {
        last = 0;
      } else {
        last = 1;
      }
      top = 1;
      return last;
    }
    if (top) {
      if (y[0] > 0) {
        last = 0;
      } else {
        last = 1;
      }
      return last;
    }
    if (y[0] + y[1] == 2) {
      if (y[0] > 0 && y[1] > 0) {
        kek += "01";
        last = 1;
        return last;
      } else if (y[0] > 0) {
        kek += "00";
        last = 0;
        return last;
      } else {
        kek += "11";
        last = 1;
        return last;
      }
    } else if (y[0] + y[1] == 1) {
      if (y[0] > 0) {
        kek += "0";
      } else {
        kek += "1";
      }
      if (!in(rev_s, kek)) {
        assert(in(s, kek));
        top = 1;
        return -1;
      } else if (!in(s, kek)) {
        assert(in(rev_s, kek));
        top = 1;
        last = kek.back() - '0';
        return last;
      } else {
        last = kek.back() - '0';
        return last;
      }
    } else {
      top = 1;
      return -1;
    }
  }
  assert(0);
}

Compilation message

Anthony.cpp: In function 'void dfs(int, int, int)':
Anthony.cpp:36:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |     for (auto [u, i] : g[v]) {
      |               ^
Anthony.cpp:43:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |       for (auto [u, i] : g[v]) {
      |                 ^
Anthony.cpp:50:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |       for (auto [u, i] : g[v]) {
      |                 ^
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:72:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |       for (auto [u, i] : g[v]) {
      |                 ^
Anthony.cpp:81:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |       for (auto [u, i] : g[v]) {
      |                 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15744 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 23 ms 14896 KB Output is correct
4 Correct 34 ms 16476 KB Output is correct
5 Correct 33 ms 16516 KB Output is correct
6 Correct 26 ms 15476 KB Output is correct
7 Correct 26 ms 15408 KB Output is correct
8 Correct 42 ms 16108 KB Output is correct
9 Correct 33 ms 16148 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15744 KB Output is correct
2 Correct 1 ms 1308 KB Output is correct
3 Correct 23 ms 14896 KB Output is correct
4 Correct 34 ms 16476 KB Output is correct
5 Correct 33 ms 16516 KB Output is correct
6 Correct 26 ms 15476 KB Output is correct
7 Correct 26 ms 15408 KB Output is correct
8 Correct 42 ms 16108 KB Output is correct
9 Correct 33 ms 16148 KB Output is correct
10 Correct 25 ms 13664 KB Output is correct
11 Correct 25 ms 13696 KB Output is correct
12 Correct 25 ms 13492 KB Output is correct
13 Correct 28 ms 13928 KB Output is correct
14 Correct 36 ms 13940 KB Output is correct
15 Correct 34 ms 14184 KB Output is correct
16 Correct 30 ms 16212 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13324 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 24 ms 12680 KB Output is correct
4 Correct 34 ms 14448 KB Output is correct
5 Correct 32 ms 14364 KB Output is correct
6 Correct 26 ms 13168 KB Output is correct
7 Correct 27 ms 13308 KB Output is correct
8 Correct 34 ms 13984 KB Output is correct
9 Correct 28 ms 13956 KB Output is correct
10 Correct 27 ms 13688 KB Output is correct
11 Correct 26 ms 13696 KB Output is correct
12 Correct 32 ms 13616 KB Output is correct
13 Correct 30 ms 13716 KB Output is correct
14 Correct 30 ms 13924 KB Output is correct
15 Correct 28 ms 14032 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 13324 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 24 ms 12680 KB Output is correct
4 Correct 34 ms 14448 KB Output is correct
5 Correct 32 ms 14364 KB Output is correct
6 Correct 26 ms 13168 KB Output is correct
7 Correct 27 ms 13308 KB Output is correct
8 Correct 34 ms 13984 KB Output is correct
9 Correct 28 ms 13956 KB Output is correct
10 Correct 27 ms 13688 KB Output is correct
11 Correct 26 ms 13696 KB Output is correct
12 Correct 32 ms 13616 KB Output is correct
13 Correct 30 ms 13716 KB Output is correct
14 Correct 30 ms 13924 KB Output is correct
15 Correct 28 ms 14032 KB Output is correct
16 Correct 23 ms 11648 KB Output is correct
17 Correct 24 ms 11744 KB Output is correct
18 Correct 26 ms 11640 KB Output is correct
19 Correct 24 ms 11820 KB Output is correct
20 Correct 26 ms 12404 KB Output is correct
21 Correct 26 ms 12080 KB Output is correct
22 Correct 31 ms 14140 KB Output is correct
23 Correct 24 ms 11684 KB Output is correct
24 Correct 25 ms 11712 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1568 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11396 KB Output is correct
2 Incorrect 24 ms 12160 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 11884 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -