oj.uz

Submission #216538

# Submission time Handle Problem Language Result Execution time Memory
216538 2020-03-27T13:13:44 Z dantoh000 Stray Cat (JOI20_stray) C++14
20 / 100
 77 ms 16788 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 (total == 0) {
            sure = true;
            return -1;
        }
        if (!sure){
            if (total > 1){
                if (sofar.empty()){
                    if (total == 2) cur = y[0]>0?0:1;
                    else{
                        sure = true;
                    }
                    sofar.push_back(cur);
                    return prv = cur;
                }
                else{
                    sure = true;
                    if (y[0]==0||y[1]==0){
                        return -1;
                    }
                    else{
                        cur = prv^1;
                        return prv = cur;
                    }
                }
            }
            else{
                if (sofar.empty()){
                    sure = true;
                    return prv = cur;
                }
                else if ((int)sofar.size() == 3){
                    sure = true;
                    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{
                    sofar.push_back(cur);
                    return prv = cur;
                }
            }
        }
        else{
            if (total >= 2){
                cur = prv^1;
            }
            assert(y[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:89: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 67 ms 15852 KB Output is correct
2 Correct 10 ms 884 KB Output is correct
3 Correct 51 ms 14976 KB Output is correct
4 Correct 73 ms 16764 KB Output is correct
5 Correct 77 ms 16788 KB Output is correct
6 Correct 54 ms 15680 KB Output is correct
7 Correct 59 ms 15612 KB Output is correct
8 Correct 71 ms 16408 KB Output is correct
9 Correct 63 ms 16416 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15852 KB Output is correct
2 Correct 10 ms 884 KB Output is correct
3 Correct 51 ms 14976 KB Output is correct
4 Correct 73 ms 16764 KB Output is correct
5 Correct 77 ms 16788 KB Output is correct
6 Correct 54 ms 15680 KB Output is correct
7 Correct 59 ms 15612 KB Output is correct
8 Correct 71 ms 16408 KB Output is correct
9 Correct 63 ms 16416 KB Output is correct
10 Correct 67 ms 13688 KB Output is correct
11 Correct 55 ms 13712 KB Output is correct
12 Correct 53 ms 13596 KB Output is correct
13 Correct 54 ms 14188 KB Output is correct
14 Correct 51 ms 13796 KB Output is correct
15 Correct 55 ms 14408 KB Output is correct
16 Correct 60 ms 16548 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13428 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 45 ms 13040 KB Output is correct
4 Correct 63 ms 14856 KB Output is correct
5 Correct 72 ms 15140 KB Output is correct
6 Correct 51 ms 13424 KB Output is correct
7 Correct 52 ms 13576 KB Output is correct
8 Correct 63 ms 14212 KB Output is correct
9 Correct 59 ms 14224 KB Output is correct
10 Correct 61 ms 13820 KB Output is correct
11 Correct 55 ms 13968 KB Output is correct
12 Correct 55 ms 13980 KB Output is correct
13 Correct 56 ms 13972 KB Output is correct
14 Correct 61 ms 14236 KB Output is correct
15 Correct 69 ms 14176 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13428 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 45 ms 13040 KB Output is correct
4 Correct 63 ms 14856 KB Output is correct
5 Correct 72 ms 15140 KB Output is correct
6 Correct 51 ms 13424 KB Output is correct
7 Correct 52 ms 13576 KB Output is correct
8 Correct 63 ms 14212 KB Output is correct
9 Correct 59 ms 14224 KB Output is correct
10 Correct 61 ms 13820 KB Output is correct
11 Correct 55 ms 13968 KB Output is correct
12 Correct 55 ms 13980 KB Output is correct
13 Correct 56 ms 13972 KB Output is correct
14 Correct 61 ms 14236 KB Output is correct
15 Correct 69 ms 14176 KB Output is correct
16 Correct 47 ms 11988 KB Output is correct
17 Correct 52 ms 11848 KB Output is correct
18 Correct 49 ms 11828 KB Output is correct
19 Correct 53 ms 11848 KB Output is correct
20 Correct 54 ms 12496 KB Output is correct
21 Correct 52 ms 12516 KB Output is correct
22 Correct 57 ms 14364 KB Output is correct
23 Correct 56 ms 11984 KB Output is correct
24 Correct 49 ms 11976 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1128 KB Output is correct
2 Correct 8 ms 780 KB Output is correct
3 Correct 10 ms 1128 KB Output is correct
4 Correct 10 ms 1260 KB Output is correct
5 Correct 10 ms 1168 KB Output is correct
6 Correct 10 ms 1104 KB Output is correct
7 Correct 10 ms 1128 KB Output is correct
8 Correct 10 ms 1132 KB Output is correct
9 Correct 10 ms 1132 KB Output is correct
10 Correct 10 ms 1040 KB Output is correct
11 Correct 10 ms 1184 KB Output is correct
12 Correct 10 ms 1128 KB Output is correct
13 Correct 11 ms 1024 KB Output is correct
14 Correct 10 ms 1252 KB Output is correct
15 Correct 10 ms 1040 KB Output is correct
16 Correct 10 ms 1040 KB Output is correct
17 Correct 10 ms 1104 KB Output is correct
18 Correct 10 ms 1104 KB Output is correct
19 Correct 10 ms 1112 KB Output is correct
20 Correct 10 ms 1108 KB Output is correct
21 Correct 10 ms 1124 KB Output is correct
22 Correct 10 ms 1148 KB Output is correct
23 Correct 10 ms 1040 KB Output is correct
24 Correct 10 ms 1148 KB Output is correct
25 Correct 10 ms 1128 KB Output is correct
26 Correct 10 ms 1132 KB Output is correct
27 Correct 10 ms 1072 KB Output is correct
28 Correct 10 ms 1260 KB Output is correct

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11640 KB Output is correct
2 Correct 53 ms 12176 KB Output is correct
3 Correct 9 ms 780 KB Output is correct
4 Correct 42 ms 11520 KB Output is correct
5 Correct 63 ms 12696 KB Output is correct
6 Correct 61 ms 12672 KB Output is correct
7 Correct 50 ms 11664 KB Output is correct
8 Correct 50 ms 11816 KB Output is correct
9 Correct 57 ms 12696 KB Output is correct
10 Correct 60 ms 12652 KB Output is correct
11 Correct 59 ms 12708 KB Output is correct
12 Correct 69 ms 12708 KB Output is correct
13 Correct 60 ms 12676 KB Output is correct
14 Correct 62 ms 12700 KB Output is correct
15 Correct 60 ms 12716 KB Output is correct
16 Correct 60 ms 12512 KB Output is correct
17 Incorrect 53 ms 12328 KB Wrong Answer [6]
18 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11644 KB Output is correct
2 Correct 51 ms 12064 KB Output is correct
3 Correct 10 ms 776 KB Output is correct
4 Correct 43 ms 11612 KB Output is correct
5 Correct 62 ms 13140 KB Output is correct
6 Correct 61 ms 12912 KB Output is correct
7 Correct 53 ms 12072 KB Output is correct
8 Correct 51 ms 12080 KB Output is correct
9 Correct 60 ms 13108 KB Output is correct
10 Correct 59 ms 12876 KB Output is correct
11 Correct 63 ms 12976 KB Output is correct
12 Correct 57 ms 12748 KB Output is correct
13 Correct 63 ms 13096 KB Output is correct
14 Correct 61 ms 12968 KB Output is correct
15 Correct 59 ms 12980 KB Output is correct
16 Correct 59 ms 12868 KB Output is correct
17 Incorrect 53 ms 12580 KB Wrong Answer [6]
18 Halted 0 ms 0 KB -