oj.uz

Submission #216550

# Submission time Handle Problem Language Result Execution time Memory
216550 2020-03-27T13:27:18 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 70 ms 17064 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
namespace {

}  // namespace
int f(int x){
    return (x == 1 || x == 3 || x == 4 || x == 5);
}
std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    vector<int> adjlist[N];
    int dist[N];
    int p[N];
    vector<int> ans;
    queue<int> q;
    for (int i = 0; i < M; i++){
        adjlist[U[i]].push_back(V[i]);
        adjlist[V[i]].push_back(U[i]);
    }
    ans.resize(M);
    if (A >= 3){
        memset(dist,-1,sizeof(dist));
        dist[0] = 0;
        p[0] = 0;
        q.push(0);
        while (q.size()){
            int u = q.front(); q.pop();
            for (auto v : adjlist[u]){
                if (dist[v] == -1){
                    //printf("%d -> %d\n",u,v);
                    p[v] = u;
                    dist[v] = dist[u]+1;
                    q.push(v);
                }
            }
        }
        for (int i = 0; i < M; i++){
            if (dist[U[i]] > dist[V[i]]) swap(U[i],V[i]);
            int d = (dist[V[i]]-dist[U[i]]);
            if (p[V[i]] == U[i]) {
                ans[i] = dist[U[i]]%3;
                //printf("edge %d-%d, dist %d,%d: mark %d\n",U[i],V[i],dist[U[i]],dist[V[i]],ans[i]);
            }
            else ans[i] = -1;

        }
        for (int i = 0; i < M; i++){
            if (ans[i] == -1){
                ans[i] = dist[U[i]]%3;
                //printf("useless edge %d-%d dist %d,%d: mark %d\n",U[i],V[i],dist[U[i]],dist[V[i]],ans[i]);
            }
        }
    }
    else{
        memset(dist,-1,sizeof(dist));
        dist[0] = 0;
        p[0] = 0;
        q.push(0);
        while (q.size()){
            int u = q.front(); q.pop();
            int branch = adjlist[u].size() > 2;
            if (branch){
                dist[u] = f(dist[p[u]])^1;
            }
            for (auto v : adjlist[u]){
                if (dist[v] == -1){
                    //printf("%d -> %d\n",u,v);
                    p[v] = u;
                    dist[v] = (dist[u]+1)%8;
                    q.push(v);
                }
            }
        }
        for (int i = 0; i < M; i++){
            if (p[U[i]] == V[i]) swap(U[i],V[i]);
            ans[i] = f(dist[U[i]]);
            //printf("%d %d %d\n",U[i],V[i],ans[i]);
        }
    }
    return ans;
}

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

int A, B;
int sure = 0;
vector<int> sofar;
int prv = -2;
}  // namespace

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

int Move(std::vector<int> y) {
    //printf("new move %d %d\n",y[0],y[1]);
    //printf("wasted %d so far, sure ? %d\n",(int)sofar.size(),sure);
    if (A >= 3){
        if (prv == -2){
            if (y[0] == 0) return prv = y[1]?1:2;
            else if (y[1] == 0) return prv = y[2]?2:0;
            else if (y[2] == 0) return prv = y[0]?0:1;
        }
        else{
            return prv = (prv+2)%3;
        }
    }
    else{
        int total = y[0]+y[1];
        int cur = y[0]==1?0:1;
        if (sure){
            if (total >= 2){
                cur = prv^1;
            }
            return prv = cur;
        }
        else if (sofar.empty()){
            if (total == 1){
                sure = true;
                return prv = cur;
            }
            else if (total == 2){
                cur = y[0]?0:1;
                sofar.push_back(cur);
                return prv = cur;
            }
            else{
                sure = true;
                return prv = cur;
            }
        }
        else if ((int)sofar.size() == 3){
            sure = true;
            if (total == 0){
                return -1;
            }
            int CUR = 4*sofar[0] + 2*sofar[1] + sofar[2];
            int need;
            if (CUR == 0 || CUR == 2 || CUR == 5 || CUR == 3) need = 0;
            else need = 1;
            //printf("so far visited %d %d %d -> %d\n",sofar[0],sofar[1],sofar[2],need);
            if (y[need] == 0){
                return -1;
            }
            else return prv = need;
        }
        else{
            if (total == 0){
                sure = true;
                return -1;
            }
            if (total > 1){
                sure = true;
                cur = prv^1;
                assert(y[cur]);
                return prv = cur;
            }
            else{
                sofar.push_back(cur);
                return prv = cur;
            }
        }
    }
}

Compilation message

Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:41:17: warning: unused variable 'd' [-Wunused-variable]
             int d = (dist[V[i]]-dist[U[i]]);
                 ^

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:86: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 55 ms 15896 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 47 ms 15448 KB Output is correct
4 Correct 70 ms 17064 KB Output is correct
5 Correct 68 ms 17052 KB Output is correct
6 Correct 54 ms 15876 KB Output is correct
7 Correct 55 ms 15872 KB Output is correct
8 Correct 69 ms 16560 KB Output is correct
9 Correct 64 ms 16560 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15896 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 47 ms 15448 KB Output is correct
4 Correct 70 ms 17064 KB Output is correct
5 Correct 68 ms 17052 KB Output is correct
6 Correct 54 ms 15876 KB Output is correct
7 Correct 55 ms 15872 KB Output is correct
8 Correct 69 ms 16560 KB Output is correct
9 Correct 64 ms 16560 KB Output is correct
10 Correct 52 ms 13876 KB Output is correct
11 Correct 51 ms 13972 KB Output is correct
12 Correct 51 ms 14000 KB Output is correct
13 Correct 50 ms 13744 KB Output is correct
14 Correct 53 ms 13992 KB Output is correct
15 Correct 56 ms 14416 KB Output is correct
16 Correct 60 ms 16812 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13704 KB Output is correct
2 Correct 10 ms 776 KB Output is correct
3 Correct 49 ms 13088 KB Output is correct
4 Correct 66 ms 15260 KB Output is correct
5 Correct 63 ms 15124 KB Output is correct
6 Correct 54 ms 13692 KB Output is correct
7 Correct 52 ms 13688 KB Output is correct
8 Correct 61 ms 14392 KB Output is correct
9 Correct 57 ms 14492 KB Output is correct
10 Correct 57 ms 14008 KB Output is correct
11 Correct 55 ms 14128 KB Output is correct
12 Correct 62 ms 14248 KB Output is correct
13 Correct 55 ms 14172 KB Output is correct
14 Correct 62 ms 14488 KB Output is correct
15 Correct 59 ms 14492 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 13704 KB Output is correct
2 Correct 10 ms 776 KB Output is correct
3 Correct 49 ms 13088 KB Output is correct
4 Correct 66 ms 15260 KB Output is correct
5 Correct 63 ms 15124 KB Output is correct
6 Correct 54 ms 13692 KB Output is correct
7 Correct 52 ms 13688 KB Output is correct
8 Correct 61 ms 14392 KB Output is correct
9 Correct 57 ms 14492 KB Output is correct
10 Correct 57 ms 14008 KB Output is correct
11 Correct 55 ms 14128 KB Output is correct
12 Correct 62 ms 14248 KB Output is correct
13 Correct 55 ms 14172 KB Output is correct
14 Correct 62 ms 14488 KB Output is correct
15 Correct 59 ms 14492 KB Output is correct
16 Correct 49 ms 11988 KB Output is correct
17 Correct 52 ms 12000 KB Output is correct
18 Correct 48 ms 11840 KB Output is correct
19 Correct 50 ms 12080 KB Output is correct
20 Correct 55 ms 12504 KB Output is correct
21 Correct 56 ms 12200 KB Output is correct
22 Correct 59 ms 14636 KB Output is correct
23 Correct 53 ms 11980 KB Output is correct
24 Correct 50 ms 12104 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1128 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 10 ms 1128 KB Output is correct
4 Correct 10 ms 1128 KB Output is correct
5 Correct 10 ms 1168 KB Output is correct
6 Correct 10 ms 1040 KB Output is correct
7 Incorrect 10 ms 1132 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11832 KB Output is correct
2 Correct 55 ms 12444 KB Output is correct
3 Correct 10 ms 776 KB Output is correct
4 Correct 44 ms 11776 KB Output is correct
5 Correct 59 ms 12968 KB Output is correct
6 Correct 65 ms 12944 KB Output is correct
7 Correct 50 ms 11924 KB Output is correct
8 Correct 52 ms 12008 KB Output is correct
9 Correct 59 ms 12848 KB Output is correct
10 Correct 60 ms 12968 KB Output is correct
11 Correct 59 ms 13060 KB Output is correct
12 Correct 61 ms 12844 KB Output is correct
13 Correct 60 ms 12976 KB Output is correct
14 Correct 60 ms 12940 KB Output is correct
15 Correct 59 ms 12956 KB Output is correct
16 Correct 59 ms 12960 KB Output is correct
17 Incorrect 50 ms 12328 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11900 KB Output is correct
2 Correct 53 ms 12100 KB Output is correct
3 Correct 9 ms 892 KB Output is correct
4 Correct 43 ms 11512 KB Output is correct
5 Correct 59 ms 12716 KB Output is correct
6 Correct 60 ms 12640 KB Output is correct
7 Correct 51 ms 11812 KB Output is correct
8 Correct 59 ms 11664 KB Output is correct
9 Correct 60 ms 12712 KB Output is correct
10 Correct 60 ms 12720 KB Output is correct
11 Correct 59 ms 12640 KB Output is correct
12 Correct 66 ms 12640 KB Output is correct
13 Correct 65 ms 12708 KB Output is correct
14 Correct 60 ms 12688 KB Output is correct
15 Correct 60 ms 12704 KB Output is correct
16 Correct 61 ms 12704 KB Output is correct
17 Incorrect 52 ms 12000 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -