oj.uz

Submission #216521

# Submission time Handle Problem Language Result Execution time Memory
216521 2020-03-27T12:49:52 Z dantoh000 Stray Cat (JOI20_stray) C++14
15 / 100
 68 ms 20092 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\n");
    //printf("wasted %d so far, sure ? %d\n",(int)sofar.size(),sure);
    //for (int j = 0; j < A; ++j) printf("%d %d\n",j,y[j]);
    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 (y[0] + y[1] == 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;
                    assert(y[cur]);
                    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);
                    assert(y[cur]);
                    return cur;
                }
            }
        }
        else{
            assert(y[cur]);
            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: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 15636 KB Output is correct
2 Correct 8 ms 776 KB Output is correct
3 Correct 47 ms 14972 KB Output is correct
4 Correct 63 ms 17056 KB Output is correct
5 Correct 68 ms 16800 KB Output is correct
6 Correct 53 ms 15376 KB Output is correct
7 Correct 53 ms 15360 KB Output is correct
8 Correct 61 ms 16404 KB Output is correct
9 Correct 60 ms 16152 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15636 KB Output is correct
2 Correct 8 ms 776 KB Output is correct
3 Correct 47 ms 14972 KB Output is correct
4 Correct 63 ms 17056 KB Output is correct
5 Correct 68 ms 16800 KB Output is correct
6 Correct 53 ms 15376 KB Output is correct
7 Correct 53 ms 15360 KB Output is correct
8 Correct 61 ms 16404 KB Output is correct
9 Correct 60 ms 16152 KB Output is correct
10 Correct 51 ms 13432 KB Output is correct
11 Correct 50 ms 13324 KB Output is correct
12 Correct 49 ms 13432 KB Output is correct
13 Correct 54 ms 13432 KB Output is correct
14 Correct 57 ms 13764 KB Output is correct
15 Correct 55 ms 14172 KB Output is correct
16 Correct 64 ms 16380 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13216 KB Output is correct
2 Correct 9 ms 788 KB Output is correct
3 Correct 45 ms 12836 KB Output is correct
4 Correct 65 ms 14624 KB Output is correct
5 Correct 63 ms 14624 KB Output is correct
6 Correct 51 ms 13416 KB Output is correct
7 Correct 51 ms 13180 KB Output is correct
8 Correct 62 ms 13980 KB Output is correct
9 Correct 56 ms 13980 KB Output is correct
10 Correct 55 ms 13720 KB Output is correct
11 Correct 55 ms 13724 KB Output is correct
12 Correct 55 ms 13652 KB Output is correct
13 Correct 57 ms 13724 KB Output is correct
14 Correct 57 ms 13980 KB Output is correct
15 Correct 59 ms 13960 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 13216 KB Output is correct
2 Correct 9 ms 788 KB Output is correct
3 Correct 45 ms 12836 KB Output is correct
4 Correct 65 ms 14624 KB Output is correct
5 Correct 63 ms 14624 KB Output is correct
6 Correct 51 ms 13416 KB Output is correct
7 Correct 51 ms 13180 KB Output is correct
8 Correct 62 ms 13980 KB Output is correct
9 Correct 56 ms 13980 KB Output is correct
10 Correct 55 ms 13720 KB Output is correct
11 Correct 55 ms 13724 KB Output is correct
12 Correct 55 ms 13652 KB Output is correct
13 Correct 57 ms 13724 KB Output is correct
14 Correct 57 ms 13980 KB Output is correct
15 Correct 59 ms 13960 KB Output is correct
16 Correct 46 ms 11640 KB Output is correct
17 Correct 47 ms 11752 KB Output is correct
18 Correct 49 ms 11612 KB Output is correct
19 Correct 49 ms 11572 KB Output is correct
20 Correct 62 ms 12216 KB Output is correct
21 Correct 50 ms 11972 KB Output is correct
22 Correct 57 ms 14200 KB Output is correct
23 Correct 50 ms 11640 KB Output is correct
24 Correct 50 ms 11708 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1112 KB Output is correct
2 Correct 8 ms 780 KB Output is correct
3 Correct 10 ms 1132 KB Output is correct
4 Correct 10 ms 1068 KB Output is correct
5 Correct 10 ms 1136 KB Output is correct
6 Correct 10 ms 1264 KB Output is correct
7 Runtime error 11 ms 1660 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 Runtime error 53 ms 20092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 19836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -