oj.uz

Submission #1081485

# Submission time Handle Problem Language Result Execution time Memory
1081485 2024-08-30T05:43:21 Z isaachew Stray Cat (JOI20_stray) C++17
100 / 100
 60 ms 19620 KB 
#include "Anthony.h"
#include <bits/stdc++.h>

namespace {
std::vector<std::vector<int>> edges;
std::map<std::pair<int,int>,int> eids;
std::vector<int> marks;
std::vector<int> visited;
void dfs(int cur,int parent,int prog){
    if(visited[cur]){
        marks[eids[{cur,parent}]]=2;
        return;
    }
    visited[cur]=1;
    if(cur!=0)marks[eids[{cur,parent}]]=(13>>(prog%6))&1;
    int oldm=(13>>(prog%6))&1;
    int nprog=edges[cur].size()==2?prog+1:oldm?4:0;
    for(int i:edges[cur]){
        if(i==parent)continue;
        dfs(i,cur,nprog);
    }
}
}  // namespace
/*
 DFS tree?
 101100 away from node 0
 001101 along the branches of the tree - if you are going the wrong way, it will be reversed
 
 
 001101
 
 01100
 11001
 10010
 00101
 01011
 10110
 all appear only in reverse
 
 If you see one of the rotations of it, go back the other way
 
 */
std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    marks.resize(M);
    edges.resize(N);
    visited.resize(N);
    for(int i=0;i<M;i++){
        eids[{U[i],V[i]}]=i;
        eids[{V[i],U[i]}]=i;
        edges[U[i]].push_back(V[i]);
        edges[V[i]].push_back(U[i]);
    }
    if(A==2){
        dfs(0,0,0);
    }else{
        std::queue<std::pair<int,int>> bfs;
        std::vector<int> dists(N,-1);
        bfs.push({0,0});
        while(!bfs.empty()){
            std::pair<int,int> cur=bfs.front();
            bfs.pop();
            if(dists[cur.first]!=-1)continue;
            dists[cur.first]=cur.second;
            for(int i:edges[cur.first]){
                if(dists[i]==-1){
                    marks[eids[{cur.first,i}]]=cur.second%3;
                    bfs.push({i,cur.second+1});
                }
            }
        }
    }
    //for(int i:marks)std::cout<<i<<'\n';
  return marks;
}

#include "Catherine.h"
#include <bits/stdc++.h>

namespace {
int tree=0;
int num=0;
int last6=-1;
int last=0;
}  // namespace
/*
 001101
 */
void Init(int A, int B) {
    if(A==2)tree=1;
}

int Move(std::vector<int> y) {
    
    /*
     std::cout<<"move "<<last<<'\n';
    std::cout<<last6<<'\n';
    std::cout<<"seen\n";
    for(int i:y){
        std::cout<<i<<' ';
    }
    std::cout<<'\n';
     */
    if(tree){
        if(num==0){
            if(y[0]+y[1]==2){
                if(y[1]==0){
                    last6=0;
                    last=0;
                }else if(y[1]==1){
                    last6=1;
                    last=1;
                }else if(y[1]==2){
                    last6=3;
                    last=1;
                }
                num=2;
                return last;//don't care
            }else{
                num=-1e9;
                last=y[1]==1;
                return last;//what appears once
            }
        }
        if(y[0]+y[1]>=2){
            num=-1e9;
            int n=y[1];
            int move;
            if(y[0]==0||y[1]==0)move=-1;
            else if((y[0]+!last)==1)move=0;
            else move=1;
            last=move==-1?last:move;
            return move;
        }else if(y[0]+y[1]==1){
            last6<<=1;last6+=y[1];num++;
            if(num==5){
                if(last6==12||last6==25||last6==18||last6==5||last6==11||last6==22){
                    num=-1e9;
                    last=last;
                    return -1;
                }
            }
            last=y[1];
            return last;
        }else{
            num=-1e9;last=last;
            return -1;
        }
    }else{
        if(y[2]==0&&y[0]!=0)return 0;
        if(y[0]==0&&y[1]!=0)return 1;
        if(y[1]==0&&y[2]!=0)return 2;
        return 12345;
    }
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:51:17: warning: unused variable 'n' [-Wunused-variable]
   51 |             int n=y[1];
      |                 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18416 KB Output is correct
2 Correct 0 ms 796 KB Output is correct
3 Correct 36 ms 18028 KB Output is correct
4 Correct 51 ms 19620 KB Output is correct
5 Correct 49 ms 19456 KB Output is correct
6 Correct 41 ms 18312 KB Output is correct
7 Correct 40 ms 18276 KB Output is correct
8 Correct 55 ms 19036 KB Output is correct
9 Correct 51 ms 19276 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18416 KB Output is correct
2 Correct 0 ms 796 KB Output is correct
3 Correct 36 ms 18028 KB Output is correct
4 Correct 51 ms 19620 KB Output is correct
5 Correct 49 ms 19456 KB Output is correct
6 Correct 41 ms 18312 KB Output is correct
7 Correct 40 ms 18276 KB Output is correct
8 Correct 55 ms 19036 KB Output is correct
9 Correct 51 ms 19276 KB Output is correct
10 Correct 40 ms 16452 KB Output is correct
11 Correct 39 ms 16368 KB Output is correct
12 Correct 39 ms 16364 KB Output is correct
13 Correct 39 ms 16404 KB Output is correct
14 Correct 40 ms 16720 KB Output is correct
15 Correct 47 ms 16716 KB Output is correct
16 Correct 60 ms 18940 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15940 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 44 ms 15784 KB Output is correct
4 Correct 56 ms 17388 KB Output is correct
5 Correct 48 ms 17460 KB Output is correct
6 Correct 39 ms 16148 KB Output is correct
7 Correct 41 ms 16064 KB Output is correct
8 Correct 44 ms 16772 KB Output is correct
9 Correct 43 ms 16712 KB Output is correct
10 Correct 39 ms 16368 KB Output is correct
11 Correct 40 ms 16584 KB Output is correct
12 Correct 54 ms 16452 KB Output is correct
13 Correct 44 ms 16472 KB Output is correct
14 Correct 49 ms 16736 KB Output is correct
15 Correct 45 ms 16752 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15940 KB Output is correct
2 Correct 0 ms 784 KB Output is correct
3 Correct 44 ms 15784 KB Output is correct
4 Correct 56 ms 17388 KB Output is correct
5 Correct 48 ms 17460 KB Output is correct
6 Correct 39 ms 16148 KB Output is correct
7 Correct 41 ms 16064 KB Output is correct
8 Correct 44 ms 16772 KB Output is correct
9 Correct 43 ms 16712 KB Output is correct
10 Correct 39 ms 16368 KB Output is correct
11 Correct 40 ms 16584 KB Output is correct
12 Correct 54 ms 16452 KB Output is correct
13 Correct 44 ms 16472 KB Output is correct
14 Correct 49 ms 16736 KB Output is correct
15 Correct 45 ms 16752 KB Output is correct
16 Correct 44 ms 14512 KB Output is correct
17 Correct 39 ms 14632 KB Output is correct
18 Correct 41 ms 14592 KB Output is correct
19 Correct 40 ms 14344 KB Output is correct
20 Correct 47 ms 15084 KB Output is correct
21 Correct 52 ms 14908 KB Output is correct
22 Correct 48 ms 16872 KB Output is correct
23 Correct 39 ms 14668 KB Output is correct
24 Correct 39 ms 14652 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1060 KB Output is correct
2 Correct 0 ms 796 KB Output is correct
3 Correct 2 ms 1308 KB Output is correct
4 Correct 2 ms 1056 KB Output is correct
5 Correct 1 ms 1052 KB Output is correct
6 Correct 2 ms 1056 KB Output is correct
7 Correct 2 ms 1048 KB Output is correct
8 Correct 1 ms 1048 KB Output is correct
9 Correct 1 ms 1040 KB Output is correct
10 Correct 2 ms 1048 KB Output is correct
11 Correct 1 ms 1056 KB Output is correct
12 Correct 2 ms 1056 KB Output is correct
13 Correct 2 ms 1056 KB Output is correct
14 Correct 1 ms 1056 KB Output is correct
15 Correct 2 ms 1056 KB Output is correct
16 Correct 2 ms 1048 KB Output is correct
17 Correct 2 ms 1472 KB Output is correct
18 Correct 2 ms 1052 KB Output is correct
19 Correct 2 ms 1052 KB Output is correct
20 Correct 1 ms 1056 KB Output is correct
21 Correct 1 ms 1060 KB Output is correct
22 Correct 2 ms 1048 KB Output is correct
23 Correct 2 ms 1040 KB Output is correct
24 Correct 1 ms 1056 KB Output is correct
25 Correct 2 ms 1048 KB Output is correct
26 Correct 2 ms 1060 KB Output is correct
27 Correct 2 ms 1048 KB Output is correct
28 Correct 1 ms 1044 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14424 KB Output is correct
2 Correct 41 ms 15708 KB Output is correct
3 Correct 1 ms 792 KB Output is correct
4 Correct 38 ms 14244 KB Output is correct
5 Correct 53 ms 17312 KB Output is correct
6 Correct 48 ms 17616 KB Output is correct
7 Correct 46 ms 16472 KB Output is correct
8 Correct 41 ms 16340 KB Output is correct
9 Correct 50 ms 17480 KB Output is correct
10 Correct 45 ms 17388 KB Output is correct
11 Correct 47 ms 17392 KB Output is correct
12 Correct 44 ms 17424 KB Output is correct
13 Correct 40 ms 17312 KB Output is correct
14 Correct 41 ms 17392 KB Output is correct
15 Correct 46 ms 17380 KB Output is correct
16 Correct 48 ms 17468 KB Output is correct
17 Correct 41 ms 17232 KB Output is correct
18 Correct 41 ms 17148 KB Output is correct
19 Correct 41 ms 17248 KB Output is correct
20 Correct 48 ms 17132 KB Output is correct
21 Correct 40 ms 17072 KB Output is correct
22 Correct 45 ms 17208 KB Output is correct
23 Correct 41 ms 14416 KB Output is correct
24 Correct 39 ms 14428 KB Output is correct
25 Correct 41 ms 14916 KB Output is correct
26 Correct 49 ms 14900 KB Output is correct
27 Correct 41 ms 15668 KB Output is correct
28 Correct 42 ms 15752 KB Output is correct
29 Correct 41 ms 15584 KB Output is correct
30 Correct 41 ms 15616 KB Output is correct
31 Correct 39 ms 14056 KB Output is correct
32 Correct 39 ms 14552 KB Output is correct
33 Correct 38 ms 14780 KB Output is correct
34 Correct 40 ms 14668 KB Output is correct
35 Correct 53 ms 15604 KB Output is correct
36 Correct 46 ms 15676 KB Output is correct
37 Correct 43 ms 15692 KB Output is correct
38 Correct 38 ms 15688 KB Output is correct
39 Correct 43 ms 15716 KB Output is correct
40 Correct 41 ms 15692 KB Output is correct
41 Correct 44 ms 16328 KB Output is correct
42 Correct 47 ms 16380 KB Output is correct
43 Correct 47 ms 16112 KB Output is correct
44 Correct 48 ms 16232 KB Output is correct
45 Correct 40 ms 16228 KB Output is correct
46 Correct 48 ms 16320 KB Output is correct
47 Correct 42 ms 15444 KB Output is correct
48 Correct 45 ms 15324 KB Output is correct
49 Correct 40 ms 15172 KB Output is correct
50 Correct 38 ms 15468 KB Output is correct
51 Correct 38 ms 14416 KB Output is correct
52 Correct 46 ms 14412 KB Output is correct
53 Correct 39 ms 14404 KB Output is correct
54 Correct 39 ms 14404 KB Output is correct
55 Correct 40 ms 14320 KB Output is correct
56 Correct 45 ms 14556 KB Output is correct
57 Correct 37 ms 14412 KB Output is correct
58 Correct 39 ms 14324 KB Output is correct
59 Correct 41 ms 14588 KB Output is correct
60 Correct 43 ms 14356 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 14148 KB Output is correct
2 Correct 44 ms 15352 KB Output is correct
3 Correct 0 ms 796 KB Output is correct
4 Correct 34 ms 13852 KB Output is correct
5 Correct 50 ms 17340 KB Output is correct
6 Correct 50 ms 17428 KB Output is correct
7 Correct 39 ms 16456 KB Output is correct
8 Correct 42 ms 16340 KB Output is correct
9 Correct 47 ms 17484 KB Output is correct
10 Correct 41 ms 17500 KB Output is correct
11 Correct 53 ms 17420 KB Output is correct
12 Correct 43 ms 17348 KB Output is correct
13 Correct 44 ms 17480 KB Output is correct
14 Correct 47 ms 17516 KB Output is correct
15 Correct 44 ms 17500 KB Output is correct
16 Correct 48 ms 17488 KB Output is correct
17 Correct 44 ms 16984 KB Output is correct
18 Correct 39 ms 17036 KB Output is correct
19 Correct 41 ms 17048 KB Output is correct
20 Correct 44 ms 17232 KB Output is correct
21 Correct 44 ms 17136 KB Output is correct
22 Correct 41 ms 17232 KB Output is correct
23 Correct 37 ms 14352 KB Output is correct
24 Correct 40 ms 14340 KB Output is correct
25 Correct 43 ms 14920 KB Output is correct
26 Correct 39 ms 14932 KB Output is correct
27 Correct 45 ms 15696 KB Output is correct
28 Correct 47 ms 15672 KB Output is correct
29 Correct 45 ms 15708 KB Output is correct
30 Correct 41 ms 15688 KB Output is correct
31 Correct 36 ms 14144 KB Output is correct
32 Correct 36 ms 14148 KB Output is correct
33 Correct 41 ms 14832 KB Output is correct
34 Correct 36 ms 14760 KB Output is correct
35 Correct 40 ms 15496 KB Output is correct
36 Correct 44 ms 15616 KB Output is correct
37 Correct 43 ms 15680 KB Output is correct
38 Correct 40 ms 15712 KB Output is correct
39 Correct 41 ms 15684 KB Output is correct
40 Correct 41 ms 15560 KB Output is correct
41 Correct 48 ms 16120 KB Output is correct
42 Correct 43 ms 16312 KB Output is correct
43 Correct 44 ms 16208 KB Output is correct
44 Correct 41 ms 16292 KB Output is correct
45 Correct 41 ms 16172 KB Output is correct
46 Correct 44 ms 16288 KB Output is correct
47 Correct 39 ms 15564 KB Output is correct
48 Correct 41 ms 15448 KB Output is correct
49 Correct 44 ms 15112 KB Output is correct
50 Correct 38 ms 15452 KB Output is correct
51 Correct 35 ms 14284 KB Output is correct
52 Correct 39 ms 14404 KB Output is correct
53 Correct 40 ms 14460 KB Output is correct
54 Correct 39 ms 14524 KB Output is correct
55 Correct 45 ms 14636 KB Output is correct
56 Correct 40 ms 14324 KB Output is correct
57 Correct 37 ms 14412 KB Output is correct
58 Correct 43 ms 14436 KB Output is correct
59 Correct 44 ms 14424 KB Output is correct
60 Correct 36 ms 14408 KB Output is correct