oj.uz

Submission #904051

# Submission time Handle Problem Language Result Execution time Memory
904051 2024-01-11T18:46:00 Z guechotjrhh Stray Cat (JOI20_stray) C++14
15 / 100
 50 ms 16724 KB 
#include "Anthony.h"
#include <vector>
#include<queue>
#include<iostream>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second


vector<int> sequ = { 0, 1, 0, 0, 1, 1 };
int n, m;
void dfs(int i, int col, int seq, int f, vector<vector<pi>>& g, vector<int>&res) {
    if (g[i].size() == 1 && f != -1) return;
    if ((g[i].size() == 2 && f != -1) || g[i].size() == 1) {
        if (seq == -1) seq = (col == 0) ? 0 : 5;
        (seq += 1) %= 6;
        int ni = (g[i][0].x == f) ? 1 : 0;
        res[g[i][ni].y] = sequ[seq];
        dfs(g[i][ni].x, sequ[seq], seq, i, g, res);
        return;
    }
    for (pi p : g[i]) {
        if (p.x == f) continue;
        res[p.y] = 1 - col;
        dfs(p.x, 1 - col, -1, i, g, res);
    }
    
}
vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    n = N; m = M;

    vector<vector<pi>> g(n);
    for (int i = 0; i < m; i++) {
        g[U[i]].push_back({ V[i],i });
        g[V[i]].push_back({ U[i],i });
    }
    if (A >= 3) {
        vector<int> dist(n, 1e9);
        dist[0] = 0;
        queue<int> q;
        q.push(0);
        while (q.size()) {
            int u = q.front(); q.pop();
            for (pi j : g[u]) {
                if (dist[j.x] > dist[u] + 1) {
                    dist[j.x] = dist[u] + 1;
                    q.push(j.x);
                }
            }
        }
        vector<int> res(m);
        for (int i = 0; i < m; i++) {
            res[i] = min(dist[U[i]] , dist[V[i]]) % 3;
        }
        return res;
    }
    else {
        vector<int> res(m);
        dfs(0, 1, -1, -1, g, res);
        return res;
    }
}

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

int v = -1,a,b;
bool flag = 0;
vector<int> last;
void Init(int A, int B) {
    a = A;
    b = B;
    v = -1;
    flag = 0;
    last.clear();
}
vector<int> seqi = { 0, 1, 0, 0, 1, 1 };
bool check() {
    for (int i = 0; i < 6; i++) {
        bool fl = 1;
        for (int j = 0; j < 5; j++) {
            if (last[j] != seqi[(i + j) % 6]) fl = 0;
        }
        if (fl) return 1;
    }
    return 0;
}
int Move(vector<int> y) {
    if (a >= 3) {
        if (v != -1) {
            (v += 2) %= 3;
            return v;
        }
        if (y[0] && !y[2]) v = 0;
        if (!y[1] && y[2]) v = 2;
        if (!y[0] && y[1]) v = 1;
        return v;
    }
    else {
        if (flag) {
            if (y[0] && y[1]) v = 1 - v;
            else if (y[0]) v = 0;
            else if (y[1]) v = 1;
            return v;
        }
        else if (v == -1) {
            if (y[0] + y[1] > 2) {
                if (y[0] > 1) v = 1;
                else v = 0;
                flag = 1;
                return v;
            }
            if (y[0] + y[1] == 1) {
                if (y[0]) v = 0;
                else v = 1;
                flag = 1;
                return v;
            }
            if (y[0]) last.push_back(0);
            if (y[1]) { v = 1; last.push_back(1);}
            if (y[0] == 2) { v = 0; last.push_back(0); }
            if (y[1] == 2) { last.push_back(1); }
            return v;
        }
        else {
            if (y[0] + y[1] > 1) {
                flag = 1;
                if (y[v]) {
                    v = 1 - v;
                    return v;
                }
                else return -1;
            }
            if (y[0] + y[1] == 0) {
                flag = 1;
                return -1;
            }
            if (y[0]) v = 0;
            else v = 1;
            last.push_back(v);
            if (last.size() < 5) return v;
            flag = 1;
            if (check()) return v;
            v = last[3];
            return -1;
        }
    }
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15700 KB Output is correct
2 Correct 1 ms 796 KB Output is correct
3 Correct 27 ms 15096 KB Output is correct
4 Correct 43 ms 16688 KB Output is correct
5 Correct 34 ms 16724 KB Output is correct
6 Correct 30 ms 15420 KB Output is correct
7 Correct 28 ms 15608 KB Output is correct
8 Correct 44 ms 16160 KB Output is correct
9 Correct 34 ms 16128 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 15700 KB Output is correct
2 Correct 1 ms 796 KB Output is correct
3 Correct 27 ms 15096 KB Output is correct
4 Correct 43 ms 16688 KB Output is correct
5 Correct 34 ms 16724 KB Output is correct
6 Correct 30 ms 15420 KB Output is correct
7 Correct 28 ms 15608 KB Output is correct
8 Correct 44 ms 16160 KB Output is correct
9 Correct 34 ms 16128 KB Output is correct
10 Correct 26 ms 13596 KB Output is correct
11 Correct 26 ms 13624 KB Output is correct
12 Correct 26 ms 13644 KB Output is correct
13 Correct 26 ms 13632 KB Output is correct
14 Correct 31 ms 13880 KB Output is correct
15 Correct 32 ms 14032 KB Output is correct
16 Correct 32 ms 16372 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13192 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 24 ms 12940 KB Output is correct
4 Correct 34 ms 14492 KB Output is correct
5 Correct 32 ms 14428 KB Output is correct
6 Correct 26 ms 13300 KB Output is correct
7 Correct 26 ms 13248 KB Output is correct
8 Correct 50 ms 13824 KB Output is correct
9 Correct 34 ms 13868 KB Output is correct
10 Correct 31 ms 13704 KB Output is correct
11 Correct 33 ms 13572 KB Output is correct
12 Correct 34 ms 13608 KB Output is correct
13 Correct 34 ms 13580 KB Output is correct
14 Correct 32 ms 13956 KB Output is correct
15 Correct 31 ms 13940 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 13192 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 24 ms 12940 KB Output is correct
4 Correct 34 ms 14492 KB Output is correct
5 Correct 32 ms 14428 KB Output is correct
6 Correct 26 ms 13300 KB Output is correct
7 Correct 26 ms 13248 KB Output is correct
8 Correct 50 ms 13824 KB Output is correct
9 Correct 34 ms 13868 KB Output is correct
10 Correct 31 ms 13704 KB Output is correct
11 Correct 33 ms 13572 KB Output is correct
12 Correct 34 ms 13608 KB Output is correct
13 Correct 34 ms 13580 KB Output is correct
14 Correct 32 ms 13956 KB Output is correct
15 Correct 31 ms 13940 KB Output is correct
16 Correct 24 ms 11672 KB Output is correct
17 Correct 24 ms 11592 KB Output is correct
18 Correct 25 ms 11592 KB Output is correct
19 Correct 34 ms 11656 KB Output is correct
20 Correct 26 ms 12320 KB Output is correct
21 Correct 31 ms 12092 KB Output is correct
22 Correct 40 ms 14132 KB Output is correct
23 Correct 30 ms 11772 KB Output is correct
24 Correct 27 ms 12096 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1136 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 1 ms 1048 KB Output is correct
4 Correct 2 ms 1076 KB Output is correct
5 Correct 2 ms 1128 KB Output is correct
6 Incorrect 2 ms 1140 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 11440 KB Output is correct
2 Correct 30 ms 12068 KB Output is correct
3 Correct 1 ms 784 KB Output is correct
4 Correct 32 ms 11052 KB Output is correct
5 Correct 31 ms 12624 KB Output is correct
6 Correct 43 ms 12648 KB Output is correct
7 Incorrect 30 ms 11560 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 11412 KB Output is correct
2 Correct 27 ms 12080 KB Output is correct
3 Correct 0 ms 796 KB Output is correct
4 Correct 22 ms 10996 KB Output is correct
5 Correct 32 ms 12480 KB Output is correct
6 Correct 44 ms 12496 KB Output is correct
7 Incorrect 28 ms 11644 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -