oj.uz

Submission #216558

# Submission time Handle Problem Language Result Execution time Memory
216558 2020-03-27T13:36:26 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 70 ms 17320 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, 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;
                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;
                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:90: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 16140 KB Output is correct
2 Correct 8 ms 1020 KB Output is correct
3 Correct 51 ms 15612 KB Output is correct
4 Correct 64 ms 17320 KB Output is correct
5 Correct 66 ms 17320 KB Output is correct
6 Correct 53 ms 15852 KB Output is correct
7 Correct 53 ms 16012 KB Output is correct
8 Correct 61 ms 16676 KB Output is correct
9 Correct 64 ms 16652 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 16140 KB Output is correct
2 Correct 8 ms 1020 KB Output is correct
3 Correct 51 ms 15612 KB Output is correct
4 Correct 64 ms 17320 KB Output is correct
5 Correct 66 ms 17320 KB Output is correct
6 Correct 53 ms 15852 KB Output is correct
7 Correct 53 ms 16012 KB Output is correct
8 Correct 61 ms 16676 KB Output is correct
9 Correct 64 ms 16652 KB Output is correct
10 Correct 53 ms 13904 KB Output is correct
11 Correct 52 ms 13768 KB Output is correct
12 Correct 60 ms 13996 KB Output is correct
13 Correct 51 ms 14012 KB Output is correct
14 Correct 70 ms 14012 KB Output is correct
15 Correct 62 ms 14532 KB Output is correct
16 Correct 65 ms 16760 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13736 KB Output is correct
2 Correct 9 ms 880 KB Output is correct
3 Correct 59 ms 13220 KB Output is correct
4 Correct 63 ms 15092 KB Output is correct
5 Correct 63 ms 15140 KB Output is correct
6 Correct 63 ms 13812 KB Output is correct
7 Correct 67 ms 13644 KB Output is correct
8 Correct 61 ms 14500 KB Output is correct
9 Correct 60 ms 14496 KB Output is correct
10 Correct 57 ms 14356 KB Output is correct
11 Correct 67 ms 14228 KB Output is correct
12 Correct 57 ms 14232 KB Output is correct
13 Correct 56 ms 14240 KB Output is correct
14 Correct 60 ms 14292 KB Output is correct
15 Correct 60 ms 14484 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13736 KB Output is correct
2 Correct 9 ms 880 KB Output is correct
3 Correct 59 ms 13220 KB Output is correct
4 Correct 63 ms 15092 KB Output is correct
5 Correct 63 ms 15140 KB Output is correct
6 Correct 63 ms 13812 KB Output is correct
7 Correct 67 ms 13644 KB Output is correct
8 Correct 61 ms 14500 KB Output is correct
9 Correct 60 ms 14496 KB Output is correct
10 Correct 57 ms 14356 KB Output is correct
11 Correct 67 ms 14228 KB Output is correct
12 Correct 57 ms 14232 KB Output is correct
13 Correct 56 ms 14240 KB Output is correct
14 Correct 60 ms 14292 KB Output is correct
15 Correct 60 ms 14484 KB Output is correct
16 Correct 47 ms 11852 KB Output is correct
17 Correct 49 ms 12020 KB Output is correct
18 Correct 50 ms 12104 KB Output is correct
19 Correct 54 ms 12152 KB Output is correct
20 Correct 57 ms 12728 KB Output is correct
21 Correct 52 ms 12472 KB Output is correct
22 Correct 63 ms 14640 KB Output is correct
23 Correct 52 ms 12260 KB Output is correct
24 Correct 50 ms 12200 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1100 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 10 ms 1132 KB Output is correct
4 Correct 10 ms 1232 KB Output is correct
5 Correct 10 ms 1132 KB Output is correct
6 Correct 10 ms 1264 KB Output is correct
7 Incorrect 10 ms 1268 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 11880 KB Output is correct
2 Correct 54 ms 12364 KB Output is correct
3 Correct 9 ms 884 KB Output is correct
4 Correct 43 ms 11748 KB Output is correct
5 Correct 60 ms 12964 KB Output is correct
6 Correct 65 ms 12952 KB Output is correct
7 Correct 51 ms 12048 KB Output is correct
8 Correct 52 ms 12068 KB Output is correct
9 Correct 60 ms 12960 KB Output is correct
10 Correct 62 ms 12876 KB Output is correct
11 Correct 60 ms 12948 KB Output is correct
12 Correct 60 ms 12896 KB Output is correct
13 Correct 59 ms 12968 KB Output is correct
14 Correct 62 ms 12964 KB Output is correct
15 Correct 63 ms 12936 KB Output is correct
16 Correct 63 ms 12964 KB Output is correct
17 Incorrect 51 ms 12272 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11888 KB Output is correct
2 Correct 54 ms 12148 KB Output is correct
3 Correct 9 ms 776 KB Output is correct
4 Correct 53 ms 11768 KB Output is correct
5 Correct 59 ms 12964 KB Output is correct
6 Correct 63 ms 12972 KB Output is correct
7 Correct 50 ms 12044 KB Output is correct
8 Correct 51 ms 11924 KB Output is correct
9 Correct 60 ms 12968 KB Output is correct
10 Correct 59 ms 12964 KB Output is correct
11 Correct 59 ms 12804 KB Output is correct
12 Correct 60 ms 12952 KB Output is correct
13 Correct 59 ms 12956 KB Output is correct
14 Correct 59 ms 12828 KB Output is correct
15 Correct 61 ms 12932 KB Output is correct
16 Correct 59 ms 12936 KB Output is correct
17 Incorrect 50 ms 12236 KB Wrong Answer [5]
18 Halted 0 ms 0 KB -