oj.uz

Submission #216528

# Submission time Handle Problem Language Result Execution time Memory
216528 2020-03-27T13:01:41 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 66 ms 21288 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 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 55 ms 15696 KB Output is correct
2 Correct 9 ms 644 KB Output is correct
3 Correct 45 ms 14976 KB Output is correct
4 Correct 66 ms 16772 KB Output is correct
5 Correct 64 ms 16628 KB Output is correct
6 Correct 53 ms 15356 KB Output is correct
7 Correct 52 ms 15364 KB Output is correct
8 Correct 60 ms 16152 KB Output is correct
9 Correct 60 ms 16280 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15696 KB Output is correct
2 Correct 9 ms 644 KB Output is correct
3 Correct 45 ms 14976 KB Output is correct
4 Correct 66 ms 16772 KB Output is correct
5 Correct 64 ms 16628 KB Output is correct
6 Correct 53 ms 15356 KB Output is correct
7 Correct 52 ms 15364 KB Output is correct
8 Correct 60 ms 16152 KB Output is correct
9 Correct 60 ms 16280 KB Output is correct
10 Correct 49 ms 13476 KB Output is correct
11 Correct 50 ms 13484 KB Output is correct
12 Correct 49 ms 13492 KB Output is correct
13 Correct 49 ms 13432 KB Output is correct
14 Correct 53 ms 13688 KB Output is correct
15 Correct 55 ms 14160 KB Output is correct
16 Correct 57 ms 16296 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13364 KB Output is correct
2 Correct 8 ms 644 KB Output is correct
3 Correct 46 ms 12796 KB Output is correct
4 Correct 61 ms 14624 KB Output is correct
5 Correct 63 ms 14628 KB Output is correct
6 Correct 51 ms 13432 KB Output is correct
7 Correct 51 ms 13320 KB Output is correct
8 Correct 66 ms 13972 KB Output is correct
9 Correct 63 ms 13976 KB Output is correct
10 Correct 55 ms 13724 KB Output is correct
11 Correct 54 ms 13736 KB Output is correct
12 Correct 55 ms 13696 KB Output is correct
13 Correct 55 ms 13692 KB Output is correct
14 Correct 55 ms 13940 KB Output is correct
15 Correct 56 ms 13980 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13364 KB Output is correct
2 Correct 8 ms 644 KB Output is correct
3 Correct 46 ms 12796 KB Output is correct
4 Correct 61 ms 14624 KB Output is correct
5 Correct 63 ms 14628 KB Output is correct
6 Correct 51 ms 13432 KB Output is correct
7 Correct 51 ms 13320 KB Output is correct
8 Correct 66 ms 13972 KB Output is correct
9 Correct 63 ms 13976 KB Output is correct
10 Correct 55 ms 13724 KB Output is correct
11 Correct 54 ms 13736 KB Output is correct
12 Correct 55 ms 13696 KB Output is correct
13 Correct 55 ms 13692 KB Output is correct
14 Correct 55 ms 13940 KB Output is correct
15 Correct 56 ms 13980 KB Output is correct
16 Correct 46 ms 11728 KB Output is correct
17 Correct 47 ms 11628 KB Output is correct
18 Correct 49 ms 11556 KB Output is correct
19 Correct 49 ms 11572 KB Output is correct
20 Correct 54 ms 12380 KB Output is correct
21 Correct 60 ms 12176 KB Output is correct
22 Correct 55 ms 14092 KB Output is correct
23 Correct 63 ms 11708 KB Output is correct
24 Correct 48 ms 11696 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1132 KB Output is correct
2 Correct 9 ms 792 KB Output is correct
3 Correct 10 ms 1256 KB Output is correct
4 Correct 10 ms 1128 KB Output is correct
5 Correct 10 ms 1140 KB Output is correct
6 Correct 10 ms 1156 KB Output is correct
7 Runtime error 10 ms 1524 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 47 ms 11608 KB Output is correct
2 Correct 52 ms 12372 KB Output is correct
3 Correct 9 ms 776 KB Output is correct
4 Correct 43 ms 11688 KB Output is correct
5 Correct 59 ms 12964 KB Output is correct
6 Correct 60 ms 12876 KB Output is correct
7 Correct 51 ms 12080 KB Output is correct
8 Correct 50 ms 12084 KB Output is correct
9 Correct 59 ms 12968 KB Output is correct
10 Correct 59 ms 12876 KB Output is correct
11 Correct 57 ms 12960 KB Output is correct
12 Correct 59 ms 12956 KB Output is correct
13 Correct 59 ms 12940 KB Output is correct
14 Correct 64 ms 12956 KB Output is correct
15 Correct 66 ms 13028 KB Output is correct
16 Correct 59 ms 12960 KB Output is correct
17 Runtime error 55 ms 21288 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 62 ms 11612 KB Output is correct
2 Runtime error 55 ms 20860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -