oj.uz

Submission #762322

# Submission time Handle Problem Language Result Execution time Memory
762322 2023-06-21T10:15:38 Z phoebe Stray Cat (JOI20_stray) C++17
15 / 100
 43 ms 16948 KB 
#include <bits/stdc++.h>
#include "Anthony.h"
using namespace std;

#define pii pair<int, int>
#define F first
#define S second

static const int maxn = 2e4 + 10;
static int n, m, a, b, 
seq[] = {0, 1, 0, 1, 1, 0},
dist[maxn];
static vector<pii> adj[maxn];
static vector<int> x;

void mark1(){
    fill(dist, dist + n, -1);
    queue<int> q; 
    q.push(0); dist[0] = 0;
    while (!q.empty()){
        int v = q.front(); q.pop();
        for (auto k : adj[v]){
            int u = k.F, i = k.S;
            if (dist[u] != -1) continue;
            dist[u] = dist[v] + 1;
            q.push(u);
        }
    }
}

void mark2(int v, int p, int last_idx){
    int cnt_children = 0, next_idx;
    for (auto k : adj[v]){
        int u = k.F, i = k.S;
        if (u != p) cnt_children++;
    }
    if (cnt_children <= 1){ // line
        next_idx = (last_idx == 5 ? 0 : last_idx + 1);
    }
    else{ // multiple children
        next_idx = (seq[last_idx] == 0 ? 1 : 0);
    }
    for (auto k : adj[v]){
        int u = k.F, i = k.S;
        if (u == p) continue;
        x[i] = seq[next_idx];
        mark2(u, v, next_idx);
    }
}

vector<int> Mark(int N, int M, int A, int B, 
vector<int> U, vector<int> V){
    n = N, m = M, a = A, b = B;
    x.resize(m, -1);
    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 >= 3){ // type 1: bfs tree; 2 -> 1 -> 0
        mark1();
        for (int v = 0; v < n; v++){
            for (auto k : adj[v]){
                int u = k.F, i = k.S;
                if (dist[u] < dist[v]) x[i] = dist[u] % 3;
                else x[i] = dist[v] % 3;
            }
        }
    }
    else{
        mark2(0, 0, 0);
        // for (int v = 0; v < n; v++){
        //     cout << v << endl;
        //     for (auto k : adj[v]){
        //         cout << "to " << k.F << ": " << x[k.S] << endl;
        //     }
        //     cout << endl;
        //     cout << endl;
        // }
    }
    return x;
}
#include <bits/stdc++.h>
#include "Catherine.h"
using namespace std;

#define pii pair<int, int>
#define F first
#define S second

static const int maxn = 2e4 + 10;
static int n, m, a, b, last = -1,
seq[] = {0, 1, 0, 1, 1, 0};
static bool is_type_1, found_direction = false, 
is_backtracking = false;
static vector<int> bruh;

void Init(int A, int B){
    a = A, b = B;
    if (a >= 3) is_type_1 = true;
    else is_type_1 = false;
}

int Move(vector<int> y){
    if (is_type_1){
        // for (auto k : y) cout << k << ' '; cout << endl;
        for (int i = 0; i < a; i++){
            int next = (i == 0 ? 2 : i - 1);
            if (y[i] > 0 && y[next] == 0) return i;
        }
        return -1;
    }
    else{
        if (found_direction){
            int cnt = y[0] + y[1] + 1, next;
            if (cnt >= 3){ // not line
                y[last]++;
                next = (y[0] < y[1] ? 0 : 1);
            }
            else{ // is line
                next = (y[0] == 0 ? 1 : 0);
            }
            last = next;
            return next;
        }
        if (is_backtracking){
            last = bruh.back(); bruh.pop_back();
            if (bruh.empty()) found_direction = true;
            return last;
        }
        else{
            vector<int> x = y;
            if (last != -1) x[last]++;
            int cnt = y[0] + y[1], next;
            if (cnt >= 3){ // not line
                found_direction = true;
                next = (y[0] < y[1] ? 0 : 1);
                last = next;
                return next;
            }
            else{
                if (last == -1){ // first one
                    if (cnt == 1){
                        found_direction = true;
                        last = (y[0] ? 0 : 1);
                    }
                    else if (y[0] == 2){
                        bruh.push_back(0);
                        last = 0;
                    }
                    else if (y[0] == 1){
                        bruh.push_back(0);
                        last = 1;
                    }
                    else if (y[0] == 0){
                        bruh.push_back(1);
                        last = 1;
                    }
                    // cout << last << endl;
                    bruh.push_back(last);
                    return last;
                }
                else if (bruh.size() <= 3){
                    last = (y[0] ? 0 : 1);
                    bruh.push_back(last);
                    return last;
                }
                else{ // completed
                    bruh.push_back(y[0] ? 0 : 1);
                    bool is_right = false;
                    for (int start = 0; start < 6; start++){
                        bool pos = true;
                        for (int i = 0; i < 5; i++){
                            if (bruh[i] != seq[(start + i) % 6]) pos = false;
                        }
                        if (pos) is_right = true;
                    }
                    if (is_right){
                        found_direction = true;
                        last = bruh.back();
                        return last;
                    }
                    else{
                        is_backtracking = true;
                        last = bruh.back(); bruh.pop_back();
                        return -1;
                    }
                }
            }
        }
    }
    return -1;
}

Compilation message

Anthony.cpp: In function 'void mark1()':
Anthony.cpp:23:26: warning: unused variable 'i' [-Wunused-variable]
   23 |             int u = k.F, i = k.S;
      |                          ^
Anthony.cpp: In function 'void mark2(int, int, int)':
Anthony.cpp:34:22: warning: unused variable 'i' [-Wunused-variable]
   34 |         int u = k.F, i = k.S;
      |                      ^

Catherine.cpp:10:15: warning: 'm' defined but not used [-Wunused-variable]
   10 | static int n, m, a, b, last = -1,
      |               ^
Catherine.cpp:10:12: warning: 'n' defined but not used [-Wunused-variable]
   10 | static int n, m, a, b, last = -1,
      |            ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15980 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 24 ms 15240 KB Output is correct
4 Correct 35 ms 16916 KB Output is correct
5 Correct 36 ms 16948 KB Output is correct
6 Correct 27 ms 15592 KB Output is correct
7 Correct 30 ms 15688 KB Output is correct
8 Correct 39 ms 16472 KB Output is correct
9 Correct 32 ms 16440 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 15980 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 24 ms 15240 KB Output is correct
4 Correct 35 ms 16916 KB Output is correct
5 Correct 36 ms 16948 KB Output is correct
6 Correct 27 ms 15592 KB Output is correct
7 Correct 30 ms 15688 KB Output is correct
8 Correct 39 ms 16472 KB Output is correct
9 Correct 32 ms 16440 KB Output is correct
10 Correct 26 ms 13808 KB Output is correct
11 Correct 31 ms 13900 KB Output is correct
12 Correct 26 ms 13880 KB Output is correct
13 Correct 33 ms 13844 KB Output is correct
14 Correct 27 ms 14056 KB Output is correct
15 Correct 30 ms 14448 KB Output is correct
16 Correct 31 ms 16512 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13460 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 22 ms 13072 KB Output is correct
4 Correct 33 ms 14888 KB Output is correct
5 Correct 33 ms 14868 KB Output is correct
6 Correct 27 ms 13536 KB Output is correct
7 Correct 30 ms 13488 KB Output is correct
8 Correct 36 ms 14104 KB Output is correct
9 Correct 43 ms 14208 KB Output is correct
10 Correct 38 ms 13800 KB Output is correct
11 Correct 28 ms 13912 KB Output is correct
12 Correct 28 ms 13888 KB Output is correct
13 Correct 27 ms 13872 KB Output is correct
14 Correct 30 ms 14320 KB Output is correct
15 Correct 30 ms 14220 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13460 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 22 ms 13072 KB Output is correct
4 Correct 33 ms 14888 KB Output is correct
5 Correct 33 ms 14868 KB Output is correct
6 Correct 27 ms 13536 KB Output is correct
7 Correct 30 ms 13488 KB Output is correct
8 Correct 36 ms 14104 KB Output is correct
9 Correct 43 ms 14208 KB Output is correct
10 Correct 38 ms 13800 KB Output is correct
11 Correct 28 ms 13912 KB Output is correct
12 Correct 28 ms 13888 KB Output is correct
13 Correct 27 ms 13872 KB Output is correct
14 Correct 30 ms 14320 KB Output is correct
15 Correct 30 ms 14220 KB Output is correct
16 Correct 23 ms 12068 KB Output is correct
17 Correct 23 ms 12092 KB Output is correct
18 Correct 25 ms 11872 KB Output is correct
19 Correct 26 ms 11948 KB Output is correct
20 Correct 27 ms 12520 KB Output is correct
21 Correct 36 ms 12256 KB Output is correct
22 Correct 30 ms 14396 KB Output is correct
23 Correct 31 ms 11976 KB Output is correct
24 Correct 26 ms 11964 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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