oj.uz

Submission #1063404

# Submission time Handle Problem Language Result Execution time Memory
1063404 2024-08-17T18:04:20 Z Andrey Stray Cat (JOI20_stray) C++14
15 / 100
 40 ms 22116 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[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:129:1: warning: control reaches end of non-void function [-Wreturn-type]
  129 | }
      | ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20808 KB Output is correct
2 Correct 3 ms 6196 KB Output is correct
3 Correct 23 ms 20556 KB Output is correct
4 Correct 33 ms 22116 KB Output is correct
5 Correct 31 ms 22004 KB Output is correct
6 Correct 28 ms 20832 KB Output is correct
7 Correct 26 ms 20860 KB Output is correct
8 Correct 32 ms 21596 KB Output is correct
9 Correct 31 ms 21600 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 20808 KB Output is correct
2 Correct 3 ms 6196 KB Output is correct
3 Correct 23 ms 20556 KB Output is correct
4 Correct 33 ms 22116 KB Output is correct
5 Correct 31 ms 22004 KB Output is correct
6 Correct 28 ms 20832 KB Output is correct
7 Correct 26 ms 20860 KB Output is correct
8 Correct 32 ms 21596 KB Output is correct
9 Correct 31 ms 21600 KB Output is correct
10 Correct 26 ms 18988 KB Output is correct
11 Correct 24 ms 19000 KB Output is correct
12 Correct 24 ms 19040 KB Output is correct
13 Correct 25 ms 19056 KB Output is correct
14 Correct 27 ms 19284 KB Output is correct
15 Correct 27 ms 19548 KB Output is correct
16 Correct 30 ms 21584 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 18528 KB Output is correct
2 Correct 2 ms 6192 KB Output is correct
3 Correct 27 ms 18184 KB Output is correct
4 Correct 32 ms 19868 KB Output is correct
5 Correct 31 ms 20068 KB Output is correct
6 Correct 26 ms 18544 KB Output is correct
7 Correct 25 ms 18712 KB Output is correct
8 Correct 32 ms 19280 KB Output is correct
9 Correct 30 ms 19280 KB Output is correct
10 Correct 27 ms 19068 KB Output is correct
11 Correct 28 ms 19040 KB Output is correct
12 Correct 27 ms 19048 KB Output is correct
13 Correct 27 ms 19052 KB Output is correct
14 Correct 28 ms 19300 KB Output is correct
15 Correct 28 ms 19284 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 18528 KB Output is correct
2 Correct 2 ms 6192 KB Output is correct
3 Correct 27 ms 18184 KB Output is correct
4 Correct 32 ms 19868 KB Output is correct
5 Correct 31 ms 20068 KB Output is correct
6 Correct 26 ms 18544 KB Output is correct
7 Correct 25 ms 18712 KB Output is correct
8 Correct 32 ms 19280 KB Output is correct
9 Correct 30 ms 19280 KB Output is correct
10 Correct 27 ms 19068 KB Output is correct
11 Correct 28 ms 19040 KB Output is correct
12 Correct 27 ms 19048 KB Output is correct
13 Correct 27 ms 19052 KB Output is correct
14 Correct 28 ms 19300 KB Output is correct
15 Correct 28 ms 19284 KB Output is correct
16 Correct 22 ms 17056 KB Output is correct
17 Correct 22 ms 16988 KB Output is correct
18 Correct 23 ms 16980 KB Output is correct
19 Correct 23 ms 16984 KB Output is correct
20 Correct 28 ms 18244 KB Output is correct
21 Correct 27 ms 17500 KB Output is correct
22 Correct 30 ms 19556 KB Output is correct
23 Correct 24 ms 17112 KB Output is correct
24 Correct 24 ms 17256 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 6200 KB Output is correct
3 Correct 2 ms 6456 KB Output is correct
4 Correct 4 ms 6712 KB Output is correct
5 Correct 4 ms 6704 KB Output is correct
6 Correct 4 ms 6712 KB Output is correct
7 Correct 2 ms 6708 KB Output is correct
8 Correct 3 ms 6672 KB Output is correct
9 Incorrect 2 ms 6704 KB Wrong Answer [5]
10 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16744 KB Output is correct
2 Correct 27 ms 18284 KB Output is correct
3 Correct 2 ms 6196 KB Output is correct
4 Correct 22 ms 16444 KB Output is correct
5 Correct 33 ms 19896 KB Output is correct
6 Correct 34 ms 19832 KB Output is correct
7 Correct 28 ms 18788 KB Output is correct
8 Correct 26 ms 18792 KB Output is correct
9 Correct 28 ms 19840 KB Output is correct
10 Correct 31 ms 19880 KB Output is correct
11 Correct 37 ms 19912 KB Output is correct
12 Correct 40 ms 19904 KB Output is correct
13 Correct 33 ms 19860 KB Output is correct
14 Correct 30 ms 19804 KB Output is correct
15 Incorrect 25 ms 18784 KB Wrong Answer [5]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 16736 KB Output is correct
2 Incorrect 24 ms 17772 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -