oj.uz

Submission #216566

# Submission time Handle Problem Language Result Execution time Memory
216566 2020-03-27T14:02:54 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 70 ms 16632 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 == 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)%6;
                    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, prev %d\n",y[0],y[1],prv);
    //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;
                if (y[cur] == 2) sofar.push_back(cur);
                else sofar.push_back(cur^1);
                sofar.push_back(cur);
                return prv = cur;
            }
            else{
                sure = true;
                assert(y[0] != 0 && y[1] != 0);
                return prv = cur;
            }
        }
        else if ((int)sofar.size() == 4){
            sure = true;
            if (total == 0){
                return -1;
            }
            int CUR = 8*sofar[0] + 4*sofar[1] + 2*sofar[2]+sofar[1];
            int need = -1;
            if (CUR == 9 || CUR == 11 || CUR == 6) need = 0;
            else if (CUR == 12 || CUR == 2 || CUR == 5) need = 1;
            //printf("so far visited %d %d %d %d -> %d\n",sofar[0],sofar[1],sofar[2],sofar[3],need);
            if (need == -1 || y[need] == 0){
                return -1;
            }
            else return prv = need;
        }
        else{
            if (total == 0){
                sure = true;
                return -1;
            }
            if (total > 1){
                sure = true;
                if (y[0] == 0 || y[1] == 0){
                    return -1;
                }
                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:92: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 59 ms 15612 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 45 ms 14972 KB Output is correct
4 Correct 65 ms 16632 KB Output is correct
5 Correct 70 ms 16556 KB Output is correct
6 Correct 53 ms 15604 KB Output is correct
7 Correct 56 ms 15360 KB Output is correct
8 Correct 62 ms 16172 KB Output is correct
9 Correct 63 ms 16252 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 15612 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 45 ms 14972 KB Output is correct
4 Correct 65 ms 16632 KB Output is correct
5 Correct 70 ms 16556 KB Output is correct
6 Correct 53 ms 15604 KB Output is correct
7 Correct 56 ms 15360 KB Output is correct
8 Correct 62 ms 16172 KB Output is correct
9 Correct 63 ms 16252 KB Output is correct
10 Correct 51 ms 13336 KB Output is correct
11 Correct 51 ms 13304 KB Output is correct
12 Correct 61 ms 13500 KB Output is correct
13 Correct 53 ms 13396 KB Output is correct
14 Correct 57 ms 13528 KB Output is correct
15 Correct 59 ms 14164 KB Output is correct
16 Correct 60 ms 16416 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13328 KB Output is correct
2 Correct 10 ms 912 KB Output is correct
3 Correct 45 ms 12820 KB Output is correct
4 Correct 62 ms 14580 KB Output is correct
5 Correct 63 ms 14756 KB Output is correct
6 Correct 52 ms 13180 KB Output is correct
7 Correct 55 ms 13420 KB Output is correct
8 Correct 60 ms 13852 KB Output is correct
9 Correct 64 ms 13976 KB Output is correct
10 Correct 55 ms 13704 KB Output is correct
11 Correct 56 ms 14024 KB Output is correct
12 Correct 55 ms 13736 KB Output is correct
13 Correct 55 ms 13848 KB Output is correct
14 Correct 57 ms 13836 KB Output is correct
15 Correct 70 ms 13980 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 13328 KB Output is correct
2 Correct 10 ms 912 KB Output is correct
3 Correct 45 ms 12820 KB Output is correct
4 Correct 62 ms 14580 KB Output is correct
5 Correct 63 ms 14756 KB Output is correct
6 Correct 52 ms 13180 KB Output is correct
7 Correct 55 ms 13420 KB Output is correct
8 Correct 60 ms 13852 KB Output is correct
9 Correct 64 ms 13976 KB Output is correct
10 Correct 55 ms 13704 KB Output is correct
11 Correct 56 ms 14024 KB Output is correct
12 Correct 55 ms 13736 KB Output is correct
13 Correct 55 ms 13848 KB Output is correct
14 Correct 57 ms 13836 KB Output is correct
15 Correct 70 ms 13980 KB Output is correct
16 Correct 47 ms 11740 KB Output is correct
17 Correct 49 ms 11612 KB Output is correct
18 Correct 49 ms 11568 KB Output is correct
19 Correct 51 ms 11548 KB Output is correct
20 Correct 55 ms 12248 KB Output is correct
21 Correct 52 ms 11988 KB Output is correct
22 Correct 62 ms 14084 KB Output is correct
23 Correct 49 ms 11564 KB Output is correct
24 Correct 51 ms 11720 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1252 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 10 ms 1252 KB Output is correct
4 Correct 11 ms 1128 KB Output is correct
5 Correct 10 ms 1104 KB Output is correct
6 Correct 10 ms 1120 KB Output is correct
7 Correct 10 ms 1036 KB Output is correct
8 Incorrect 11 ms 1132 KB Wrong Answer [5]
9 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11628 KB Output is correct
2 Correct 53 ms 12080 KB Output is correct
3 Correct 9 ms 1020 KB Output is correct
4 Correct 43 ms 11500 KB Output is correct
5 Correct 59 ms 12556 KB Output is correct
6 Incorrect 47 ms 11684 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11504 KB Output is correct
2 Correct 51 ms 11668 KB Output is correct
3 Correct 8 ms 784 KB Output is correct
4 Correct 44 ms 11272 KB Output is correct
5 Correct 66 ms 12532 KB Output is correct
6 Incorrect 47 ms 11688 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -