oj.uz

Submission #1063485

# Submission time Handle Problem Language Result Execution time Memory
1063485 2024-08-17T19:17:30 Z Andrey Stray Cat (JOI20_stray) C++14
15 / 100
 37 ms 24972 KB 
#include "Anthony.h"
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> haha[200001];
vector<int> dp(200001,-1);
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;
                }
            }
        }
        x++;
        dp[a] = x;
        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 20608 KB Output is correct
2 Correct 2 ms 6180 KB Output is correct
3 Correct 24 ms 19932 KB Output is correct
4 Correct 32 ms 21632 KB Output is correct
5 Correct 32 ms 21676 KB Output is correct
6 Correct 26 ms 20364 KB Output is correct
7 Correct 26 ms 20372 KB Output is correct
8 Correct 31 ms 21132 KB Output is correct
9 Correct 30 ms 20948 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 20608 KB Output is correct
2 Correct 2 ms 6180 KB Output is correct
3 Correct 24 ms 19932 KB Output is correct
4 Correct 32 ms 21632 KB Output is correct
5 Correct 32 ms 21676 KB Output is correct
6 Correct 26 ms 20364 KB Output is correct
7 Correct 26 ms 20372 KB Output is correct
8 Correct 31 ms 21132 KB Output is correct
9 Correct 30 ms 20948 KB Output is correct
10 Correct 23 ms 18568 KB Output is correct
11 Correct 25 ms 18576 KB Output is correct
12 Correct 24 ms 18484 KB Output is correct
13 Correct 23 ms 18580 KB Output is correct
14 Correct 25 ms 18768 KB Output is correct
15 Correct 30 ms 19112 KB Output is correct
16 Correct 27 ms 21288 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18136 KB Output is correct
2 Correct 2 ms 6184 KB Output is correct
3 Correct 26 ms 17804 KB Output is correct
4 Correct 32 ms 19588 KB Output is correct
5 Correct 37 ms 19428 KB Output is correct
6 Correct 24 ms 18060 KB Output is correct
7 Correct 25 ms 18240 KB Output is correct
8 Correct 28 ms 18840 KB Output is correct
9 Correct 28 ms 18820 KB Output is correct
10 Correct 27 ms 18564 KB Output is correct
11 Correct 27 ms 18456 KB Output is correct
12 Correct 27 ms 18580 KB Output is correct
13 Correct 29 ms 18500 KB Output is correct
14 Correct 30 ms 18852 KB Output is correct
15 Correct 33 ms 18692 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18136 KB Output is correct
2 Correct 2 ms 6184 KB Output is correct
3 Correct 26 ms 17804 KB Output is correct
4 Correct 32 ms 19588 KB Output is correct
5 Correct 37 ms 19428 KB Output is correct
6 Correct 24 ms 18060 KB Output is correct
7 Correct 25 ms 18240 KB Output is correct
8 Correct 28 ms 18840 KB Output is correct
9 Correct 28 ms 18820 KB Output is correct
10 Correct 27 ms 18564 KB Output is correct
11 Correct 27 ms 18456 KB Output is correct
12 Correct 27 ms 18580 KB Output is correct
13 Correct 29 ms 18500 KB Output is correct
14 Correct 30 ms 18852 KB Output is correct
15 Correct 33 ms 18692 KB Output is correct
16 Correct 22 ms 16632 KB Output is correct
17 Correct 20 ms 16528 KB Output is correct
18 Correct 24 ms 16736 KB Output is correct
19 Correct 24 ms 16524 KB Output is correct
20 Correct 27 ms 17144 KB Output is correct
21 Correct 24 ms 17020 KB Output is correct
22 Correct 27 ms 19084 KB Output is correct
23 Correct 24 ms 16776 KB Output is correct
24 Correct 24 ms 16784 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6460 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 6540 KB Output is correct
5 Correct 4 ms 6704 KB Output is correct
6 Correct 2 ms 6708 KB Output is correct
7 Correct 3 ms 6712 KB Output is correct
8 Correct 3 ms 6712 KB Output is correct
9 Correct 2 ms 6712 KB Output is correct
10 Correct 4 ms 6964 KB Output is correct
11 Correct 4 ms 6704 KB Output is correct
12 Runtime error 4 ms 6972 KB Execution killed with signal 4
13 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 24964 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 25 ms 24972 KB Execution killed with signal 4
2 Halted 0 ms 0 KB -