oj.uz

Submission #1063405

# Submission time Handle Problem Language Result Execution time Memory
1063405 2024-08-17T18:05:46 Z Andrey Stray Cat (JOI20_stray) C++14
15 / 100
 41 ms 27744 KB 
#include "Anthony.h"
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> haha[200001];
vector<int> dp(200001);
vector<int> troll(0);
int bruhseq[6] = {0,1,0,0,1,1};

void dfs(int a, int t, int d) {
    int br = 0,x = -1;
    for(pair<int,int> v: haha[a]) {
        if(v.first != t) {
            dfs(v.first,a,d+1);
            br++;
            x = dp[v.first];
        }
    }
    if(br == 1) {
        dp[a] = x+1;
        for(auto v: haha[a]) {
            if(v.first != t) {
                if(x == -1) {
                    troll[v.second] = d%2;
                }
                else {
                    troll[v.second] = bruhseq[x%6];
                }
            }
        }
    }
    else {
        dp[a] = -1;
        for(pair<int,int> v: haha[a]) {
            if(v.first != t) {
                troll[v.second] = d%2;
            }
        }
    }
}

std::vector<int> Mark(int n, int m, int a, int b, std::vector<int> u, std::vector<int> v) {
    for(int i = 0; i < m; i++) {
        haha[u[i]].push_back({v[i],i});
        haha[v[i]].push_back({u[i],i});
    }
    if(a > 2) {
        vector<int> br(n,INT_MAX);
        br[0] = 0;
        queue<int> idk;
        idk.push(0);
        vector<int> ans(m,-1);
        while(!idk.empty()) {
            int u = idk.front();
            idk.pop();
            for(pair<int,int> v: haha[u]) {
                if(br[v.first] == INT_MAX) {
                    br[v.first] = br[u]+1;
                    idk.push(v.first);
                }
            }
        }
        for(int i = 0; i < m; i++) {
            if(ans[i] == -1) {
                int c = min(br[u[i]],br[v[i]])%3;
                ans[i] = c;
            }
        }
        return ans;
    }
    else {
        troll.resize(n-1);
        dfs(0,-1,1);
        return troll;
    }
}

#include "Catherine.h"
#include<bits/stdc++.h>
using namespace std;

int A;
int seq[6] = {0,1,0,0,1,1};
vector<int> wow(0);
bool first = true;
bool yeah = true;

void Init(int a, int b) {
    A = a;
}

int Move(vector<int> haha) {
    if(A > 2) {
        vector<int> wow(0);
        for(int i = 0; i < haha.size(); i++) {
            if(haha[i] >= 1) {
                wow.push_back(i);
            }
        }
        if(wow.size() == 1) {
            return wow[0];
        }
        else if(wow.size() == 2) {
            if(wow[0] == 0 && wow[1] == 1) {
                return 0;
            }
            else if(wow[0] == 1 && wow[1] == 2) {
                return 1;
            }
            else {
                return 2;
            }
        }
    }
    else {
        if(first) {
            first = false;
            if(haha[1] > 0 && (haha[0] > 1 || haha[0] == 0)) {
                yeah = false;
                wow.push_back(1);
                return 1;
            }
            else if(haha[0] > 0 && (haha[1] == 0 || haha[1] > 1)) {
                yeah = false;
                wow.push_back(0);
                return 0;
            }
            else {
                wow.push_back(0);
                return 0;
            }
        }
        else {
            if(yeah) {
                if(haha[0]+haha[1] == 0) {
                    yeah = false;
                    return -1;
                }
                else if(haha[0]+haha[1] > 1) {
                    yeah = false;
                    if(haha[0] == 0 || haha[1] == 0) {
                        return -1;
                    }
                    else {
                        if(wow[wow.size()-1] == 1) {
                            wow.push_back(0);
                            return 0;
                        }
                        else {
                            wow.push_back(1);
                            return 1;
                        }
                    }
                }
                else if(wow.size() == 6) {
                    for(int i = 0; i < 6; i++) {
                        bool bubu = true;
                        for(int j = i; j < i+6; j++) {
                            if(seq[j-i] != wow[j%6]) {
                                bubu = false;
                            }
                        }
                        if(bubu) {
                            yeah = false;
                            break;
                        }
                    }
                    if(yeah) {
                        yeah = false;
                        return -1;
                    }
                    else {
                        if(haha[0] > 0) {
                            wow.push_back(0);
                            return 0;
                        }
                        else {
                            wow.push_back(1);
                            return 1;
                        }
                    }
                }
                else {
                    if(haha[0] > 0) {
                        wow.push_back(0);
                        return 0;
                    }
                    else {
                        wow.push_back(1);
                        return 1;
                    }
                }
            }
            else {
                if(haha[0]+haha[1] == 0) {
                    return 1/0;
                }
                if(haha[1] > 0 && (haha[0] == 0 || wow[wow.size()-1] == 0)) {
                    wow.push_back(1);
                    return 1;
                }
                else {
                    wow.push_back(0);
                    return 0;
                }
            }
        }
    }
}

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:18:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i = 0; i < haha.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
Catherine.cpp:119:29: warning: division by zero [-Wdiv-by-zero]
  119 |                     return 1/0;
      |                            ~^~
Catherine.cpp:132:1: warning: control reaches end of non-void function [-Wreturn-type]
  132 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20964 KB Output is correct
2 Correct 2 ms 6188 KB Output is correct
3 Correct 23 ms 20368 KB Output is correct
4 Correct 35 ms 22136 KB Output is correct
5 Correct 32 ms 22168 KB Output is correct
6 Correct 32 ms 20692 KB Output is correct
7 Correct 26 ms 20832 KB Output is correct
8 Correct 31 ms 21592 KB Output is correct
9 Correct 41 ms 21684 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 20964 KB Output is correct
2 Correct 2 ms 6188 KB Output is correct
3 Correct 23 ms 20368 KB Output is correct
4 Correct 35 ms 22136 KB Output is correct
5 Correct 32 ms 22168 KB Output is correct
6 Correct 32 ms 20692 KB Output is correct
7 Correct 26 ms 20832 KB Output is correct
8 Correct 31 ms 21592 KB Output is correct
9 Correct 41 ms 21684 KB Output is correct
10 Correct 25 ms 19040 KB Output is correct
11 Correct 28 ms 18904 KB Output is correct
12 Correct 26 ms 18928 KB Output is correct
13 Correct 27 ms 18992 KB Output is correct
14 Correct 27 ms 19292 KB Output is correct
15 Correct 28 ms 19540 KB Output is correct
16 Correct 35 ms 21620 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18472 KB Output is correct
2 Correct 3 ms 6200 KB Output is correct
3 Correct 23 ms 18248 KB Output is correct
4 Correct 31 ms 20068 KB Output is correct
5 Correct 30 ms 19900 KB Output is correct
6 Correct 27 ms 18448 KB Output is correct
7 Correct 25 ms 18460 KB Output is correct
8 Correct 32 ms 19300 KB Output is correct
9 Correct 31 ms 19252 KB Output is correct
10 Correct 28 ms 19044 KB Output is correct
11 Correct 27 ms 19044 KB Output is correct
12 Correct 27 ms 19028 KB Output is correct
13 Correct 31 ms 19008 KB Output is correct
14 Correct 32 ms 19292 KB Output is correct
15 Correct 32 ms 19372 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 18472 KB Output is correct
2 Correct 3 ms 6200 KB Output is correct
3 Correct 23 ms 18248 KB Output is correct
4 Correct 31 ms 20068 KB Output is correct
5 Correct 30 ms 19900 KB Output is correct
6 Correct 27 ms 18448 KB Output is correct
7 Correct 25 ms 18460 KB Output is correct
8 Correct 32 ms 19300 KB Output is correct
9 Correct 31 ms 19252 KB Output is correct
10 Correct 28 ms 19044 KB Output is correct
11 Correct 27 ms 19044 KB Output is correct
12 Correct 27 ms 19028 KB Output is correct
13 Correct 31 ms 19008 KB Output is correct
14 Correct 32 ms 19292 KB Output is correct
15 Correct 32 ms 19372 KB Output is correct
16 Correct 22 ms 16980 KB Output is correct
17 Correct 24 ms 16988 KB Output is correct
18 Correct 24 ms 17064 KB Output is correct
19 Correct 24 ms 16956 KB Output is correct
20 Correct 33 ms 17576 KB Output is correct
21 Correct 25 ms 17500 KB Output is correct
22 Correct 28 ms 19608 KB Output is correct
23 Correct 25 ms 17036 KB Output is correct
24 Correct 28 ms 17244 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6456 KB Output is correct
2 Correct 2 ms 6196 KB Output is correct
3 Correct 3 ms 6456 KB Output is correct
4 Correct 3 ms 6716 KB Output is correct
5 Correct 3 ms 6708 KB Output is correct
6 Correct 3 ms 6708 KB Output is correct
7 Correct 2 ms 6712 KB Output is correct
8 Correct 2 ms 6712 KB Output is correct
9 Runtime error 4 ms 6968 KB Execution killed with signal 4
10 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 16812 KB Output is correct
2 Correct 28 ms 18288 KB Output is correct
3 Correct 2 ms 6188 KB Output is correct
4 Correct 20 ms 16608 KB Output is correct
5 Correct 30 ms 19812 KB Output is correct
6 Correct 28 ms 19808 KB Output is correct
7 Correct 26 ms 19052 KB Output is correct
8 Correct 26 ms 18796 KB Output is correct
9 Correct 28 ms 19816 KB Output is correct
10 Correct 30 ms 20068 KB Output is correct
11 Correct 31 ms 19824 KB Output is correct
12 Correct 32 ms 19764 KB Output is correct
13 Correct 28 ms 19884 KB Output is correct
14 Correct 34 ms 20060 KB Output is correct
15 Runtime error 29 ms 27744 KB Execution killed with signal 4
16 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16736 KB Output is correct
2 Runtime error 27 ms 26544 KB Execution killed with signal 4
3 Halted 0 ms 0 KB -