oj.uz

Submission #1000727

# Submission time Handle Problem Language Result Execution time Memory
1000727 2024-06-18T07:42:34 Z Unforgettablepl Stray Cat (JOI20_stray) C++17
100 / 100
 68 ms 16792 KB 
#include <bits/stdc++.h>
using namespace std;

namespace {


vector<int> strat1(int N, int M, int A, int B,
                vector<int> U, std::vector<int> V) {
    // General Graph A=3
    vector<int> ans(M,-1);
    vector<vector<pair<int,int>>> adj(N);
    for(int i=0;i<M;i++){
        adj[U[i]].emplace_back(V[i],i);
        adj[V[i]].emplace_back(U[i],i);
    }
    vector<bool> visited(N);
    queue<pair<int,int>> q;
    q.emplace(0,0);
    while(!q.empty()){
        auto [idx,col] = q.front();q.pop();
        if(visited[idx])continue;
        visited[idx]=true;
        for(auto&i:adj[idx]){
            if(ans[i.second]==-1)ans[i.second]=col;
            if(!visited[i.first])q.emplace(i.first,(col+1)%3);
        }
    }
    return ans;
}


vector<bool> magic = {1,1,0,0,1,0};
vector<vector<pair<int,int>>> adj;
vector<bool> ans;

void dfs(int x,int p,bool parcol,int seqidx){
    if(adj[x].size()==1)return;
    if(adj[x].size()==2){
        // Colour using sequence
        seqidx = (seqidx+1)%6;
        if(adj[x][0].first==p)swap(adj[x][0],adj[x][1]);
        if(magic[seqidx]){
            ans[adj[x][0].second]=true;
            dfs(adj[x][0].first,x,true,seqidx);
        } else {
            dfs(adj[x][0].first,x,false,seqidx);
        }
        return;
    }
    // Colour using b&w
    for(auto&i:adj[x])if(i.first!=p){
        if(parcol){
            dfs(i.first,x,false,2);
        } else {
            ans[i.second]=true;
            dfs(i.first,x,true,0);
        }
    }
}

vector<int> strat2(int N, int M, int A, int B,
                vector<int> U, std::vector<int> V) {
    // Tree A=2,B=6
    adj = vector<vector<pair<int,int>>>(N);
    ans = vector<bool>(M);
    for(int i=0;i<M;i++){
        adj[U[i]].emplace_back(V[i],i);
        adj[V[i]].emplace_back(U[i],i);
    }
    for(auto&i:adj[0]){
        dfs(i.first,0,false,2);
    }
    vector<int> col(M);
    for(int i=0;i<M;i++)if(ans[i])col[i]=1;
    return col;
}

}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                vector<int> U, std::vector<int> V) {
    if(A>=3)return strat1(N,M,A,B,U,V);
    else return strat2(N,M,A,B,U,V);
}
#include <bits/stdc++.h>
using namespace std;

namespace {

int A, B;
int strat1(vector<int> y) {
    // General Graph A=3
    bool more0 = y[0]>0;
    bool more1 = y[1]>0;
    bool more2 = y[2]>0;
    if(more0 and more1)return 0;
    if(more1 and more2)return 1;
    if(more2 and more0)return 2;
    if(more0)return 0;
    if(more1)return 1;
    if(more2)return 2;
    assert(false);
}

vector<bool> magic = {1,1,0,0,1,0};

vector<vector<int>> good = {
    {0,1,1,0,0},
    {1,0,1,1,0},
    {0,1,0,1,1},
    {0,0,1,0,1},
    {1,0,0,1,0},
    {1,1,0,0,1},
};

// False phase is detection phase
// True phase is travelling phase
bool phase = false;
int lastmov = -1;

vector<int> currseq;

int strat2(vector<int> y) {
    // Tree A=2,B=6
    if(phase){
        if(y[0]==1 and y[1]==1)y[lastmov]++;
        if(y[0]==1){
            lastmov = 0;
            return 0;
        }
        lastmov = 1;
        return 1;
    }
    if((y[0]==0 and y[1]==0) or (lastmov==-1 and y[0]+y[1]<2)){
        // We are at a leaf
        phase = true;
        if(lastmov==-1){
            if(y[0]==1){
                lastmov = 0;
                return 0;
            }
            assert(y[1]);
            lastmov = 1;
            return 1;
        }
        return -1;
    }
    // Emplace current situation into sequence
    if(lastmov==-1){
        if(y[0]+y[1]>2){ // Non-line node
            phase = true;
            if(y[0]==1){
                lastmov = 0;
                return 0;
            }
            lastmov = 1;
            return 1;
        }
        if(y[0]==2){
            currseq = {0,0};
            lastmov = 0;
            return 0;
        } else if(y[1]==2){
            currseq = {1,1};
            lastmov = 1;
            return 1;
        } else {
            currseq = {0,1};
            lastmov = 1;
            return 1;
        }
    } else {
        if(y[0]+y[1]>=2){ // Non-line node
            y[lastmov]++;
            phase = true;
            if(y[0]==1){
                if(lastmov==0)return -1;
                lastmov = 0;
                return 0;
            }
            if(lastmov==1)return -1;
            lastmov = 1;
            return 1;
        }
        if(y[0]==1){
            currseq.emplace_back(0);
            if(currseq.size()!=5){
                lastmov = 0;
                return 0;
            }
        } else {
            currseq.emplace_back(1);
            if(currseq.size()!=5){
                lastmov = 1;
                return 1;
            }
        }
    }
    if(currseq.size()==5){
        phase = true;
        if(find(good.begin(),good.end(),currseq)==good.end())return strat2(y);
        else return -1;
    }
    assert(false);
}

}  // namespace

void Init(int A, int B) {
    ::A = A;
    ::B = B;
}

int Move(vector<int> y) {
    if(A>=3)return strat1(y);
    else return strat2(y);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15952 KB Output is correct
2 Correct 1 ms 784 KB Output is correct
3 Correct 22 ms 15252 KB Output is correct
4 Correct 53 ms 16756 KB Output is correct
5 Correct 31 ms 16792 KB Output is correct
6 Correct 42 ms 15824 KB Output is correct
7 Correct 25 ms 15716 KB Output is correct
8 Correct 68 ms 16656 KB Output is correct
9 Correct 30 ms 16252 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 15952 KB Output is correct
2 Correct 1 ms 784 KB Output is correct
3 Correct 22 ms 15252 KB Output is correct
4 Correct 53 ms 16756 KB Output is correct
5 Correct 31 ms 16792 KB Output is correct
6 Correct 42 ms 15824 KB Output is correct
7 Correct 25 ms 15716 KB Output is correct
8 Correct 68 ms 16656 KB Output is correct
9 Correct 30 ms 16252 KB Output is correct
10 Correct 26 ms 13760 KB Output is correct
11 Correct 32 ms 13644 KB Output is correct
12 Correct 24 ms 13588 KB Output is correct
13 Correct 37 ms 13548 KB Output is correct
14 Correct 26 ms 13892 KB Output is correct
15 Correct 39 ms 14120 KB Output is correct
16 Correct 53 ms 16268 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13620 KB Output is correct
2 Correct 0 ms 1300 KB Output is correct
3 Correct 27 ms 12844 KB Output is correct
4 Correct 38 ms 14636 KB Output is correct
5 Correct 35 ms 14568 KB Output is correct
6 Correct 24 ms 13404 KB Output is correct
7 Correct 24 ms 13412 KB Output is correct
8 Correct 28 ms 14120 KB Output is correct
9 Correct 31 ms 14040 KB Output is correct
10 Correct 32 ms 13712 KB Output is correct
11 Correct 27 ms 13688 KB Output is correct
12 Correct 27 ms 13664 KB Output is correct
13 Correct 26 ms 13696 KB Output is correct
14 Correct 32 ms 13940 KB Output is correct
15 Correct 31 ms 13876 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 13620 KB Output is correct
2 Correct 0 ms 1300 KB Output is correct
3 Correct 27 ms 12844 KB Output is correct
4 Correct 38 ms 14636 KB Output is correct
5 Correct 35 ms 14568 KB Output is correct
6 Correct 24 ms 13404 KB Output is correct
7 Correct 24 ms 13412 KB Output is correct
8 Correct 28 ms 14120 KB Output is correct
9 Correct 31 ms 14040 KB Output is correct
10 Correct 32 ms 13712 KB Output is correct
11 Correct 27 ms 13688 KB Output is correct
12 Correct 27 ms 13664 KB Output is correct
13 Correct 26 ms 13696 KB Output is correct
14 Correct 32 ms 13940 KB Output is correct
15 Correct 31 ms 13876 KB Output is correct
16 Correct 20 ms 11860 KB Output is correct
17 Correct 28 ms 11796 KB Output is correct
18 Correct 23 ms 11708 KB Output is correct
19 Correct 23 ms 11688 KB Output is correct
20 Correct 26 ms 12484 KB Output is correct
21 Correct 24 ms 12092 KB Output is correct
22 Correct 28 ms 14236 KB Output is correct
23 Correct 24 ms 11916 KB Output is correct
24 Correct 32 ms 11848 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11776 KB Output is correct
2 Correct 24 ms 12392 KB Output is correct
3 Correct 1 ms 784 KB Output is correct
4 Correct 21 ms 11564 KB Output is correct
5 Correct 32 ms 13104 KB Output is correct
6 Correct 29 ms 13116 KB Output is correct
7 Correct 26 ms 12124 KB Output is correct
8 Correct 25 ms 12124 KB Output is correct
9 Correct 32 ms 13068 KB Output is correct
10 Correct 28 ms 12948 KB Output is correct
11 Correct 28 ms 13148 KB Output is correct
12 Correct 28 ms 13108 KB Output is correct
13 Correct 27 ms 13136 KB Output is correct
14 Correct 33 ms 13160 KB Output is correct
15 Correct 30 ms 13220 KB Output is correct
16 Correct 28 ms 13140 KB Output is correct
17 Correct 28 ms 12892 KB Output is correct
18 Correct 26 ms 12880 KB Output is correct
19 Correct 26 ms 12892 KB Output is correct
20 Correct 31 ms 12916 KB Output is correct
21 Correct 26 ms 12884 KB Output is correct
22 Correct 31 ms 12872 KB Output is correct
23 Correct 24 ms 11568 KB Output is correct
24 Correct 22 ms 11776 KB Output is correct
25 Correct 23 ms 11868 KB Output is correct
26 Correct 24 ms 11872 KB Output is correct
27 Correct 25 ms 12632 KB Output is correct
28 Correct 25 ms 12440 KB Output is correct
29 Correct 27 ms 12628 KB Output is correct
30 Correct 26 ms 12616 KB Output is correct
31 Correct 26 ms 11716 KB Output is correct
32 Correct 26 ms 11708 KB Output is correct
33 Correct 22 ms 11856 KB Output is correct
34 Correct 23 ms 11944 KB Output is correct
35 Correct 26 ms 12372 KB Output is correct
36 Correct 24 ms 12384 KB Output is correct
37 Correct 28 ms 12528 KB Output is correct
38 Correct 28 ms 12384 KB Output is correct
39 Correct 25 ms 12452 KB Output is correct
40 Correct 25 ms 12368 KB Output is correct
41 Correct 26 ms 12824 KB Output is correct
42 Correct 26 ms 12644 KB Output is correct
43 Correct 26 ms 12636 KB Output is correct
44 Correct 26 ms 12648 KB Output is correct
45 Correct 34 ms 12704 KB Output is correct
46 Correct 26 ms 12608 KB Output is correct
47 Correct 29 ms 12376 KB Output is correct
48 Correct 24 ms 12380 KB Output is correct
49 Correct 24 ms 12388 KB Output is correct
50 Correct 25 ms 12380 KB Output is correct
51 Correct 24 ms 11844 KB Output is correct
52 Correct 23 ms 11600 KB Output is correct
53 Correct 25 ms 11664 KB Output is correct
54 Correct 25 ms 11612 KB Output is correct
55 Correct 32 ms 11564 KB Output is correct
56 Correct 24 ms 11608 KB Output is correct
57 Correct 22 ms 11872 KB Output is correct
58 Correct 26 ms 11868 KB Output is correct
59 Correct 26 ms 12128 KB Output is correct
60 Correct 25 ms 12384 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11604 KB Output is correct
2 Correct 29 ms 12360 KB Output is correct
3 Correct 0 ms 784 KB Output is correct
4 Correct 20 ms 11584 KB Output is correct
5 Correct 30 ms 13120 KB Output is correct
6 Correct 32 ms 13136 KB Output is correct
7 Correct 23 ms 12120 KB Output is correct
8 Correct 34 ms 12224 KB Output is correct
9 Correct 33 ms 13140 KB Output is correct
10 Correct 32 ms 13156 KB Output is correct
11 Correct 32 ms 13072 KB Output is correct
12 Correct 27 ms 13048 KB Output is correct
13 Correct 27 ms 13140 KB Output is correct
14 Correct 30 ms 13096 KB Output is correct
15 Correct 39 ms 13140 KB Output is correct
16 Correct 32 ms 13148 KB Output is correct
17 Correct 26 ms 12704 KB Output is correct
18 Correct 28 ms 12880 KB Output is correct
19 Correct 26 ms 12596 KB Output is correct
20 Correct 26 ms 12712 KB Output is correct
21 Correct 26 ms 12884 KB Output is correct
22 Correct 29 ms 12936 KB Output is correct
23 Correct 20 ms 11852 KB Output is correct
24 Correct 25 ms 11608 KB Output is correct
25 Correct 22 ms 11876 KB Output is correct
26 Correct 23 ms 11812 KB Output is correct
27 Correct 26 ms 12628 KB Output is correct
28 Correct 25 ms 12636 KB Output is correct
29 Correct 25 ms 12476 KB Output is correct
30 Correct 26 ms 12628 KB Output is correct
31 Correct 25 ms 11624 KB Output is correct
32 Correct 23 ms 11604 KB Output is correct
33 Correct 28 ms 11872 KB Output is correct
34 Correct 28 ms 11884 KB Output is correct
35 Correct 28 ms 12624 KB Output is correct
36 Correct 26 ms 12344 KB Output is correct
37 Correct 27 ms 12376 KB Output is correct
38 Correct 24 ms 12428 KB Output is correct
39 Correct 27 ms 12372 KB Output is correct
40 Correct 25 ms 12372 KB Output is correct
41 Correct 26 ms 12640 KB Output is correct
42 Correct 38 ms 12824 KB Output is correct
43 Correct 29 ms 12580 KB Output is correct
44 Correct 33 ms 12536 KB Output is correct
45 Correct 25 ms 12624 KB Output is correct
46 Correct 31 ms 12616 KB Output is correct
47 Correct 27 ms 12284 KB Output is correct
48 Correct 24 ms 12452 KB Output is correct
49 Correct 24 ms 12256 KB Output is correct
50 Correct 24 ms 12376 KB Output is correct
51 Correct 22 ms 11848 KB Output is correct
52 Correct 24 ms 11672 KB Output is correct
53 Correct 24 ms 11608 KB Output is correct
54 Correct 25 ms 11692 KB Output is correct
55 Correct 22 ms 11724 KB Output is correct
56 Correct 25 ms 11876 KB Output is correct
57 Correct 25 ms 11904 KB Output is correct
58 Correct 25 ms 11828 KB Output is correct
59 Correct 24 ms 12096 KB Output is correct
60 Correct 24 ms 12104 KB Output is correct