oj.uz

Submission #762291

# Submission time Handle Problem Language Result Execution time Memory
762291 2023-06-21T09:08:34 Z phoebe Stray Cat (JOI20_stray) C++17
15 / 100
 35 ms 17004 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; // {{node, par}, last colour}
    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;
            }
        }
        // for (int v = 0; v < n; v++){
        //     cout << v << ": dist = " << dist[v] << endl;
        //     for (auto k : adj[v]){
        //         cout << "to " << k.F << ": " << x[k.S] << endl;
        //     }
        //     cout << endl;
        //     cout << endl;
        // }
    }
    else{
        mark2(0, 0, 0);
    }
    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;

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;
        }
    }
    else{
        cout << 'b';
        return -1;
    }
    return -1;
}

Compilation message

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

Catherine.cpp:11:1: warning: 'seq' defined but not used [-Wunused-variable]
   11 | seq[] = {0, 1, 0, 1, 1, 0};
      | ^~~
Catherine.cpp:10:24: warning: 'last' defined but not used [-Wunused-variable]
   10 | static int n, m, a, b, last = -1,
      |                        ^~~~
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 32 ms 15936 KB Output is correct
2 Correct 1 ms 1076 KB Output is correct
3 Correct 32 ms 15132 KB Output is correct
4 Correct 34 ms 17004 KB Output is correct
5 Correct 35 ms 16892 KB Output is correct
6 Correct 27 ms 15752 KB Output is correct
7 Correct 27 ms 15632 KB Output is correct
8 Correct 35 ms 16316 KB Output is correct
9 Correct 34 ms 16512 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 15936 KB Output is correct
2 Correct 1 ms 1076 KB Output is correct
3 Correct 32 ms 15132 KB Output is correct
4 Correct 34 ms 17004 KB Output is correct
5 Correct 35 ms 16892 KB Output is correct
6 Correct 27 ms 15752 KB Output is correct
7 Correct 27 ms 15632 KB Output is correct
8 Correct 35 ms 16316 KB Output is correct
9 Correct 34 ms 16512 KB Output is correct
10 Correct 26 ms 13808 KB Output is correct
11 Correct 26 ms 13708 KB Output is correct
12 Correct 27 ms 13800 KB Output is correct
13 Correct 25 ms 13812 KB Output is correct
14 Correct 27 ms 14008 KB Output is correct
15 Correct 28 ms 14448 KB Output is correct
16 Correct 30 ms 16492 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13512 KB Output is correct
2 Correct 1 ms 1040 KB Output is correct
3 Correct 22 ms 13052 KB Output is correct
4 Correct 34 ms 14808 KB Output is correct
5 Correct 32 ms 14844 KB Output is correct
6 Correct 27 ms 13444 KB Output is correct
7 Correct 27 ms 13520 KB Output is correct
8 Correct 30 ms 14064 KB Output is correct
9 Correct 28 ms 14052 KB Output is correct
10 Correct 31 ms 13908 KB Output is correct
11 Correct 35 ms 13864 KB Output is correct
12 Correct 28 ms 13916 KB Output is correct
13 Correct 27 ms 13892 KB Output is correct
14 Correct 33 ms 14288 KB Output is correct
15 Correct 30 ms 14284 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13512 KB Output is correct
2 Correct 1 ms 1040 KB Output is correct
3 Correct 22 ms 13052 KB Output is correct
4 Correct 34 ms 14808 KB Output is correct
5 Correct 32 ms 14844 KB Output is correct
6 Correct 27 ms 13444 KB Output is correct
7 Correct 27 ms 13520 KB Output is correct
8 Correct 30 ms 14064 KB Output is correct
9 Correct 28 ms 14052 KB Output is correct
10 Correct 31 ms 13908 KB Output is correct
11 Correct 35 ms 13864 KB Output is correct
12 Correct 28 ms 13916 KB Output is correct
13 Correct 27 ms 13892 KB Output is correct
14 Correct 33 ms 14288 KB Output is correct
15 Correct 30 ms 14284 KB Output is correct
16 Correct 22 ms 11960 KB Output is correct
17 Correct 23 ms 12020 KB Output is correct
18 Correct 27 ms 11916 KB Output is correct
19 Correct 30 ms 11812 KB Output is correct
20 Correct 27 ms 12536 KB Output is correct
21 Correct 27 ms 12412 KB Output is correct
22 Correct 31 ms 14324 KB Output is correct
23 Correct 28 ms 12084 KB Output is correct
24 Correct 28 ms 11972 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

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