oj.uz

Submission #216517

# Submission time Handle Problem Language Result Execution time Memory
216517 2020-03-27T12:37:34 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 65 ms 16816 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\n");
    //printf("wasted %d so far, sure ? %d\n",(int)sofar.size(),sure);
    //for (int j = 0; j < A; ++j) printf("%d %d\n",j,y[j]);
    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{
        if (!sure){
            int total = y[0]+y[1];
            if (total > 1){
                if (sofar.empty()){
                    int choose;
                    if (y[0] + y[1] == 2) choose = y[0]?0:1;
                    else{
                        sure = true;
                        assert(y[0]==1||y[1]==1);
                        choose = y[0]==1?0:1;
                    }
                    sofar.push_back(choose);
                    return choose;
                }
                else{
                    sure = true;
                    if (y[0]==0||y[1]==0){
                        return -1;
                    }
                    else{
                        return y[0]==1?0:1;
                    }
                }
            }
            else if (total == 0){
                sure = true;
                return -1;
            }
            else{
                int cur = y[0] == 1?0:1;
                if ((int)sofar.size() == 0){
                    sure = true;
                    return cur;
                }
                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 = 1;
                    else need = 0;
                    //printf("so far visited %d %d %d -> %d\n",sofar[0],sofar[1],sofar[2],need);
                    if (cur == need){
                        return -1;
                    }
                    else return cur;
                }
                else{
                    sofar.push_back(cur);
                    return cur;
                }
            }
        }
        else{
            return y[0]==1?0:1;
        }
    }

}

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 55 ms 15624 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 45 ms 14728 KB Output is correct
4 Correct 64 ms 16816 KB Output is correct
5 Correct 65 ms 16804 KB Output is correct
6 Correct 55 ms 15360 KB Output is correct
7 Correct 53 ms 15612 KB Output is correct
8 Correct 64 ms 16144 KB Output is correct
9 Correct 62 ms 16124 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15624 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 45 ms 14728 KB Output is correct
4 Correct 64 ms 16816 KB Output is correct
5 Correct 65 ms 16804 KB Output is correct
6 Correct 55 ms 15360 KB Output is correct
7 Correct 53 ms 15612 KB Output is correct
8 Correct 64 ms 16144 KB Output is correct
9 Correct 62 ms 16124 KB Output is correct
10 Correct 53 ms 13448 KB Output is correct
11 Correct 51 ms 13484 KB Output is correct
12 Correct 50 ms 13504 KB Output is correct
13 Correct 50 ms 13500 KB Output is correct
14 Correct 50 ms 13772 KB Output is correct
15 Correct 56 ms 14176 KB Output is correct
16 Correct 59 ms 16284 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13224 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 44 ms 12848 KB Output is correct
4 Correct 64 ms 14628 KB Output is correct
5 Correct 62 ms 14628 KB Output is correct
6 Correct 52 ms 13404 KB Output is correct
7 Correct 51 ms 13176 KB Output is correct
8 Correct 57 ms 13968 KB Output is correct
9 Correct 56 ms 13820 KB Output is correct
10 Correct 54 ms 13724 KB Output is correct
11 Correct 55 ms 13728 KB Output is correct
12 Correct 55 ms 13716 KB Output is correct
13 Correct 59 ms 13716 KB Output is correct
14 Correct 61 ms 13940 KB Output is correct
15 Correct 56 ms 13976 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 13224 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 44 ms 12848 KB Output is correct
4 Correct 64 ms 14628 KB Output is correct
5 Correct 62 ms 14628 KB Output is correct
6 Correct 52 ms 13404 KB Output is correct
7 Correct 51 ms 13176 KB Output is correct
8 Correct 57 ms 13968 KB Output is correct
9 Correct 56 ms 13820 KB Output is correct
10 Correct 54 ms 13724 KB Output is correct
11 Correct 55 ms 13728 KB Output is correct
12 Correct 55 ms 13716 KB Output is correct
13 Correct 59 ms 13716 KB Output is correct
14 Correct 61 ms 13940 KB Output is correct
15 Correct 56 ms 13976 KB Output is correct
16 Correct 47 ms 11756 KB Output is correct
17 Correct 46 ms 11756 KB Output is correct
18 Correct 47 ms 11552 KB Output is correct
19 Correct 49 ms 11536 KB Output is correct
20 Correct 56 ms 12368 KB Output is correct
21 Correct 51 ms 11888 KB Output is correct
22 Correct 57 ms 14236 KB Output is correct
23 Correct 48 ms 11716 KB Output is correct
24 Correct 49 ms 11692 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 11628 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 11620 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -