oj.uz

Submission #216530

# Submission time Handle Problem Language Result Execution time Memory
216530 2020-03-27T13:04:32 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 79 ms 21276 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 > 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{
                        return prv = cur;
                    }
                }
            }
            else if (total == 0){
                sure = true;
                return -1;
            }
            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:88: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 16148 KB Output is correct
2 Correct 10 ms 776 KB Output is correct
3 Correct 47 ms 15484 KB Output is correct
4 Correct 79 ms 17308 KB Output is correct
5 Correct 67 ms 17324 KB Output is correct
6 Correct 62 ms 15876 KB Output is correct
7 Correct 55 ms 15880 KB Output is correct
8 Correct 65 ms 16660 KB Output is correct
9 Correct 64 ms 16588 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16148 KB Output is correct
2 Correct 10 ms 776 KB Output is correct
3 Correct 47 ms 15484 KB Output is correct
4 Correct 79 ms 17308 KB Output is correct
5 Correct 67 ms 17324 KB Output is correct
6 Correct 62 ms 15876 KB Output is correct
7 Correct 55 ms 15880 KB Output is correct
8 Correct 65 ms 16660 KB Output is correct
9 Correct 64 ms 16588 KB Output is correct
10 Correct 51 ms 13888 KB Output is correct
11 Correct 59 ms 14016 KB Output is correct
12 Correct 50 ms 13860 KB Output is correct
13 Correct 51 ms 14000 KB Output is correct
14 Correct 51 ms 14140 KB Output is correct
15 Correct 65 ms 14404 KB Output is correct
16 Correct 66 ms 16808 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13692 KB Output is correct
2 Correct 9 ms 992 KB Output is correct
3 Correct 45 ms 13360 KB Output is correct
4 Correct 76 ms 15132 KB Output is correct
5 Correct 65 ms 15136 KB Output is correct
6 Correct 54 ms 13652 KB Output is correct
7 Correct 53 ms 13684 KB Output is correct
8 Correct 74 ms 14416 KB Output is correct
9 Correct 63 ms 14328 KB Output is correct
10 Correct 72 ms 14036 KB Output is correct
11 Correct 56 ms 14248 KB Output is correct
12 Correct 56 ms 14224 KB Output is correct
13 Correct 62 ms 14148 KB Output is correct
14 Correct 66 ms 14360 KB Output is correct
15 Correct 60 ms 14468 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13692 KB Output is correct
2 Correct 9 ms 992 KB Output is correct
3 Correct 45 ms 13360 KB Output is correct
4 Correct 76 ms 15132 KB Output is correct
5 Correct 65 ms 15136 KB Output is correct
6 Correct 54 ms 13652 KB Output is correct
7 Correct 53 ms 13684 KB Output is correct
8 Correct 74 ms 14416 KB Output is correct
9 Correct 63 ms 14328 KB Output is correct
10 Correct 72 ms 14036 KB Output is correct
11 Correct 56 ms 14248 KB Output is correct
12 Correct 56 ms 14224 KB Output is correct
13 Correct 62 ms 14148 KB Output is correct
14 Correct 66 ms 14360 KB Output is correct
15 Correct 60 ms 14468 KB Output is correct
16 Correct 59 ms 12064 KB Output is correct
17 Correct 53 ms 11852 KB Output is correct
18 Correct 62 ms 12092 KB Output is correct
19 Correct 56 ms 11972 KB Output is correct
20 Correct 56 ms 12620 KB Output is correct
21 Correct 56 ms 12480 KB Output is correct
22 Correct 60 ms 14596 KB Output is correct
23 Correct 56 ms 12228 KB Output is correct
24 Correct 53 ms 12104 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1040 KB Output is correct
2 Correct 10 ms 888 KB Output is correct
3 Correct 10 ms 1100 KB Output is correct
4 Correct 10 ms 1048 KB Output is correct
5 Correct 10 ms 1104 KB Output is correct
6 Correct 11 ms 1116 KB Output is correct
7 Runtime error 11 ms 1500 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 11820 KB Output is correct
2 Correct 56 ms 12412 KB Output is correct
3 Correct 10 ms 1020 KB Output is correct
4 Correct 48 ms 11700 KB Output is correct
5 Correct 60 ms 12876 KB Output is correct
6 Correct 66 ms 12908 KB Output is correct
7 Correct 55 ms 12060 KB Output is correct
8 Correct 57 ms 12020 KB Output is correct
9 Correct 74 ms 12944 KB Output is correct
10 Correct 70 ms 12884 KB Output is correct
11 Correct 65 ms 12964 KB Output is correct
12 Correct 70 ms 12760 KB Output is correct
13 Correct 61 ms 12756 KB Output is correct
14 Correct 69 ms 12960 KB Output is correct
15 Correct 62 ms 12816 KB Output is correct
16 Correct 77 ms 12940 KB Output is correct
17 Runtime error 67 ms 21276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11876 KB Output is correct
2 Runtime error 62 ms 20692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -