oj.uz

Submission #216551

# Submission time Handle Problem Language Result Execution time Memory
216551 2020-03-27T13:28:21 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 76 ms 21284 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 >= 2){
                cur = prv^1;
            }
            assert(y[cur]);
            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;
                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:87: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 64 ms 16136 KB Output is correct
2 Correct 9 ms 912 KB Output is correct
3 Correct 47 ms 15268 KB Output is correct
4 Correct 63 ms 17324 KB Output is correct
5 Correct 65 ms 17320 KB Output is correct
6 Correct 54 ms 15748 KB Output is correct
7 Correct 54 ms 15860 KB Output is correct
8 Correct 61 ms 16512 KB Output is correct
9 Correct 61 ms 16536 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 16136 KB Output is correct
2 Correct 9 ms 912 KB Output is correct
3 Correct 47 ms 15268 KB Output is correct
4 Correct 63 ms 17324 KB Output is correct
5 Correct 65 ms 17320 KB Output is correct
6 Correct 54 ms 15748 KB Output is correct
7 Correct 54 ms 15860 KB Output is correct
8 Correct 61 ms 16512 KB Output is correct
9 Correct 61 ms 16536 KB Output is correct
10 Correct 49 ms 13740 KB Output is correct
11 Correct 51 ms 13700 KB Output is correct
12 Correct 51 ms 13768 KB Output is correct
13 Correct 52 ms 13620 KB Output is correct
14 Correct 53 ms 14048 KB Output is correct
15 Correct 57 ms 14416 KB Output is correct
16 Correct 59 ms 16512 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13468 KB Output is correct
2 Correct 9 ms 648 KB Output is correct
3 Correct 45 ms 13096 KB Output is correct
4 Correct 72 ms 14880 KB Output is correct
5 Correct 62 ms 14888 KB Output is correct
6 Correct 53 ms 13568 KB Output is correct
7 Correct 52 ms 13696 KB Output is correct
8 Correct 57 ms 14236 KB Output is correct
9 Correct 61 ms 14080 KB Output is correct
10 Correct 59 ms 14376 KB Output is correct
11 Correct 55 ms 13968 KB Output is correct
12 Correct 56 ms 13980 KB Output is correct
13 Correct 55 ms 13968 KB Output is correct
14 Correct 62 ms 14236 KB Output is correct
15 Correct 59 ms 14248 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13468 KB Output is correct
2 Correct 9 ms 648 KB Output is correct
3 Correct 45 ms 13096 KB Output is correct
4 Correct 72 ms 14880 KB Output is correct
5 Correct 62 ms 14888 KB Output is correct
6 Correct 53 ms 13568 KB Output is correct
7 Correct 52 ms 13696 KB Output is correct
8 Correct 57 ms 14236 KB Output is correct
9 Correct 61 ms 14080 KB Output is correct
10 Correct 59 ms 14376 KB Output is correct
11 Correct 55 ms 13968 KB Output is correct
12 Correct 56 ms 13980 KB Output is correct
13 Correct 55 ms 13968 KB Output is correct
14 Correct 62 ms 14236 KB Output is correct
15 Correct 59 ms 14248 KB Output is correct
16 Correct 52 ms 12008 KB Output is correct
17 Correct 46 ms 11812 KB Output is correct
18 Correct 56 ms 11828 KB Output is correct
19 Correct 49 ms 12044 KB Output is correct
20 Correct 56 ms 12500 KB Output is correct
21 Correct 53 ms 12232 KB Output is correct
22 Correct 71 ms 14340 KB Output is correct
23 Correct 49 ms 11968 KB Output is correct
24 Correct 52 ms 11968 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1040 KB Output is correct
2 Correct 9 ms 1016 KB Output is correct
3 Correct 11 ms 1128 KB Output is correct
4 Correct 10 ms 1128 KB Output is correct
5 Correct 11 ms 1128 KB Output is correct
6 Correct 11 ms 1136 KB Output is correct
7 Runtime error 10 ms 1520 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 50 ms 11736 KB Output is correct
2 Correct 57 ms 12236 KB Output is correct
3 Correct 9 ms 776 KB Output is correct
4 Correct 43 ms 11620 KB Output is correct
5 Correct 70 ms 12748 KB Output is correct
6 Correct 60 ms 12808 KB Output is correct
7 Correct 68 ms 12032 KB Output is correct
8 Correct 53 ms 11924 KB Output is correct
9 Correct 74 ms 12820 KB Output is correct
10 Correct 71 ms 12884 KB Output is correct
11 Correct 76 ms 12948 KB Output is correct
12 Correct 70 ms 12872 KB Output is correct
13 Correct 61 ms 12964 KB Output is correct
14 Correct 66 ms 12960 KB Output is correct
15 Correct 59 ms 12964 KB Output is correct
16 Correct 60 ms 12968 KB Output is correct
17 Runtime error 56 ms 21280 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 51 ms 11892 KB Output is correct
2 Correct 53 ms 12320 KB Output is correct
3 Correct 9 ms 648 KB Output is correct
4 Correct 44 ms 11788 KB Output is correct
5 Correct 59 ms 12960 KB Output is correct
6 Correct 59 ms 12804 KB Output is correct
7 Correct 50 ms 12072 KB Output is correct
8 Correct 50 ms 12080 KB Output is correct
9 Correct 67 ms 12756 KB Output is correct
10 Correct 59 ms 12876 KB Output is correct
11 Correct 60 ms 12804 KB Output is correct
12 Correct 60 ms 12952 KB Output is correct
13 Correct 60 ms 12964 KB Output is correct
14 Correct 59 ms 12960 KB Output is correct
15 Correct 59 ms 12876 KB Output is correct
16 Correct 59 ms 12952 KB Output is correct
17 Runtime error 60 ms 21284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -