oj.uz

Submission #216526

# Submission time Handle Problem Language Result Execution time Memory
216526 2020-03-27T12:55:11 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 68 ms 16828 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;
                    }
                    assert(y[cur]);
                    sofar.push_back(cur);
                    return cur;
                }
                else{
                    sure = true;
                    if (y[0]==0||y[1]==0){
                        return -1;
                    }
                    else{
                        assert(y[cur]);
                        return cur;
                    }
                }
            }
            else if (total == 0){
                sure = true;
                return -1;
            }
            else{
                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 = 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 cur;
                }
            }
        }
        else{
            return 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:86: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 54 ms 15640 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 46 ms 14992 KB Output is correct
4 Correct 66 ms 16828 KB Output is correct
5 Correct 64 ms 16792 KB Output is correct
6 Correct 53 ms 15356 KB Output is correct
7 Correct 54 ms 15492 KB Output is correct
8 Correct 68 ms 16244 KB Output is correct
9 Correct 60 ms 16148 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15640 KB Output is correct
2 Correct 9 ms 776 KB Output is correct
3 Correct 46 ms 14992 KB Output is correct
4 Correct 66 ms 16828 KB Output is correct
5 Correct 64 ms 16792 KB Output is correct
6 Correct 53 ms 15356 KB Output is correct
7 Correct 54 ms 15492 KB Output is correct
8 Correct 68 ms 16244 KB Output is correct
9 Correct 60 ms 16148 KB Output is correct
10 Correct 50 ms 13312 KB Output is correct
11 Correct 49 ms 13484 KB Output is correct
12 Correct 50 ms 13504 KB Output is correct
13 Correct 50 ms 13504 KB Output is correct
14 Correct 54 ms 13688 KB Output is correct
15 Correct 56 ms 14144 KB Output is correct
16 Correct 59 ms 16296 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13312 KB Output is correct
2 Correct 8 ms 1020 KB Output is correct
3 Correct 45 ms 12972 KB Output is correct
4 Correct 63 ms 14632 KB Output is correct
5 Correct 62 ms 14632 KB Output is correct
6 Correct 51 ms 13172 KB Output is correct
7 Correct 54 ms 13196 KB Output is correct
8 Correct 57 ms 13964 KB Output is correct
9 Correct 56 ms 13984 KB Output is correct
10 Correct 55 ms 13692 KB Output is correct
11 Correct 63 ms 13684 KB Output is correct
12 Correct 55 ms 13708 KB Output is correct
13 Correct 56 ms 13716 KB Output is correct
14 Correct 59 ms 13944 KB Output is correct
15 Correct 60 ms 13980 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 13312 KB Output is correct
2 Correct 8 ms 1020 KB Output is correct
3 Correct 45 ms 12972 KB Output is correct
4 Correct 63 ms 14632 KB Output is correct
5 Correct 62 ms 14632 KB Output is correct
6 Correct 51 ms 13172 KB Output is correct
7 Correct 54 ms 13196 KB Output is correct
8 Correct 57 ms 13964 KB Output is correct
9 Correct 56 ms 13984 KB Output is correct
10 Correct 55 ms 13692 KB Output is correct
11 Correct 63 ms 13684 KB Output is correct
12 Correct 55 ms 13708 KB Output is correct
13 Correct 56 ms 13716 KB Output is correct
14 Correct 59 ms 13944 KB Output is correct
15 Correct 60 ms 13980 KB Output is correct
16 Correct 47 ms 11756 KB Output is correct
17 Correct 52 ms 11884 KB Output is correct
18 Correct 48 ms 11556 KB Output is correct
19 Correct 51 ms 11588 KB Output is correct
20 Correct 54 ms 12172 KB Output is correct
21 Correct 52 ms 11964 KB Output is correct
22 Correct 55 ms 14084 KB Output is correct
23 Correct 49 ms 11720 KB Output is correct
24 Correct 50 ms 11680 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1256 KB Output is correct
2 Correct 9 ms 784 KB Output is correct
3 Correct 10 ms 1116 KB Output is correct
4 Correct 10 ms 1104 KB Output is correct
5 Correct 10 ms 1260 KB Output is correct
6 Correct 11 ms 1136 KB Output is correct
7 Incorrect 10 ms 1240 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 11620 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 11768 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -