oj.uz

Submission #1063475

# Submission time Handle Problem Language Result Execution time Memory
1063475 2024-08-17T19:14:18 Z Andrey Stray Cat (JOI20_stray) C++14
15 / 100
 50 ms 25044 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, pair<int,int> usl) {
    int br = 0,x = -1;
    for(pair<int,int> v: haha[a]) {
        if(v.first != t) {
            br++;
        }
    }
    if(br != 1) {
        usl = {d,d%2};   
    }
    for(pair<int,int> v: haha[a]) {
        if(v.first != t) {
            dfs(v.first,a,d+1,usl);
            x = dp[v.first];
        }
    }
    if(br == 1) {
        if(x == -1) {
            for(int i = 0; i < 6; i++) {
                if(bruhseq[i] == d%2 && (usl.first == -1 || bruhseq[(i+(usl.first-d))%6]%2 == usl.second)) {
                    x = i-1;
                    break;
                }
            }
        }
        dp[a] = x+1;
        for(auto v: haha[a]) {
            if(v.first != t) {
                troll[v.second] = bruhseq[x%6];
            }
        }
    }
    else {
        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,{-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[0]+haha[1] == 2) {
                if(haha[0] > 0) {
                    wow.push_back(0);
                    return 0;
                }
                else {
                    wow.push_back(1);
                    return 1;
                }
            }
            else {
                yeah = false;
                if(haha[0] == 1) {
                    wow.push_back(0);
                    return 0;
                }
                else {
                    wow.push_back(1);
                    return 1;
                }
            }
        }
        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:126:29: warning: division by zero [-Wdiv-by-zero]
  126 |                     return 1/0;
      |                            ~^~
Catherine.cpp:139:1: warning: control reaches end of non-void function [-Wreturn-type]
  139 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 21080 KB Output is correct
2 Correct 3 ms 6196 KB Output is correct
3 Correct 27 ms 20456 KB Output is correct
4 Correct 39 ms 21964 KB Output is correct
5 Correct 38 ms 22096 KB Output is correct
6 Correct 33 ms 20776 KB Output is correct
7 Correct 28 ms 20900 KB Output is correct
8 Correct 38 ms 21452 KB Output is correct
9 Correct 35 ms 21472 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 21080 KB Output is correct
2 Correct 3 ms 6196 KB Output is correct
3 Correct 27 ms 20456 KB Output is correct
4 Correct 39 ms 21964 KB Output is correct
5 Correct 38 ms 22096 KB Output is correct
6 Correct 33 ms 20776 KB Output is correct
7 Correct 28 ms 20900 KB Output is correct
8 Correct 38 ms 21452 KB Output is correct
9 Correct 35 ms 21472 KB Output is correct
10 Correct 32 ms 19012 KB Output is correct
11 Correct 34 ms 18816 KB Output is correct
12 Correct 26 ms 18744 KB Output is correct
13 Correct 28 ms 19032 KB Output is correct
14 Correct 32 ms 19076 KB Output is correct
15 Correct 35 ms 19536 KB Output is correct
16 Correct 40 ms 21500 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18516 KB Output is correct
2 Correct 3 ms 6400 KB Output is correct
3 Correct 27 ms 18024 KB Output is correct
4 Correct 47 ms 20004 KB Output is correct
5 Correct 33 ms 20044 KB Output is correct
6 Correct 27 ms 18608 KB Output is correct
7 Correct 28 ms 18628 KB Output is correct
8 Correct 32 ms 19316 KB Output is correct
9 Correct 34 ms 19296 KB Output is correct
10 Correct 31 ms 19012 KB Output is correct
11 Correct 34 ms 18968 KB Output is correct
12 Correct 30 ms 19044 KB Output is correct
13 Correct 32 ms 18932 KB Output is correct
14 Correct 50 ms 19172 KB Output is correct
15 Correct 37 ms 19376 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18516 KB Output is correct
2 Correct 3 ms 6400 KB Output is correct
3 Correct 27 ms 18024 KB Output is correct
4 Correct 47 ms 20004 KB Output is correct
5 Correct 33 ms 20044 KB Output is correct
6 Correct 27 ms 18608 KB Output is correct
7 Correct 28 ms 18628 KB Output is correct
8 Correct 32 ms 19316 KB Output is correct
9 Correct 34 ms 19296 KB Output is correct
10 Correct 31 ms 19012 KB Output is correct
11 Correct 34 ms 18968 KB Output is correct
12 Correct 30 ms 19044 KB Output is correct
13 Correct 32 ms 18932 KB Output is correct
14 Correct 50 ms 19172 KB Output is correct
15 Correct 37 ms 19376 KB Output is correct
16 Correct 32 ms 16896 KB Output is correct
17 Correct 31 ms 17012 KB Output is correct
18 Correct 36 ms 17016 KB Output is correct
19 Correct 33 ms 16884 KB Output is correct
20 Correct 32 ms 17820 KB Output is correct
21 Correct 27 ms 17564 KB Output is correct
22 Correct 33 ms 19316 KB Output is correct
23 Correct 25 ms 17244 KB Output is correct
24 Correct 27 ms 17228 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 6708 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 25044 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 24924 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -