oj.uz

Submission #1063495

# Submission time Handle Problem Language Result Execution time Memory
1063495 2024-08-17T19:31:31 Z Andrey Stray Cat (JOI20_stray) C++14
15 / 100
 3000 ms 21676 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((usl.first == -1 || bruhseq[(i+(d-usl.first))%6]%2 == usl.second)) {
                    x = i-1;
                    break;
                }
            }
        }
        x++;
        if(bruhseq[x%6] != d%2) {
            for(pair<int,int> v: haha[a]) {
                if(v.first != t) {
                    dfs(v.first,a,d+2,usl);
                    x = dp[v.first];
                }
            }
        }
        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});
        /*for(int i = 0; i < troll.size(); i++) {
            cout << troll[i] << " ";
        }
        cout << endl;*/
        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 27 ms 20612 KB Output is correct
2 Correct 2 ms 6188 KB Output is correct
3 Correct 24 ms 19968 KB Output is correct
4 Correct 31 ms 21676 KB Output is correct
5 Correct 33 ms 21652 KB Output is correct
6 Correct 27 ms 20368 KB Output is correct
7 Correct 26 ms 20356 KB Output is correct
8 Correct 33 ms 21044 KB Output is correct
9 Correct 30 ms 21132 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20612 KB Output is correct
2 Correct 2 ms 6188 KB Output is correct
3 Correct 24 ms 19968 KB Output is correct
4 Correct 31 ms 21676 KB Output is correct
5 Correct 33 ms 21652 KB Output is correct
6 Correct 27 ms 20368 KB Output is correct
7 Correct 26 ms 20356 KB Output is correct
8 Correct 33 ms 21044 KB Output is correct
9 Correct 30 ms 21132 KB Output is correct
10 Correct 23 ms 18568 KB Output is correct
11 Correct 23 ms 18432 KB Output is correct
12 Correct 25 ms 18560 KB Output is correct
13 Correct 27 ms 18520 KB Output is correct
14 Correct 32 ms 18824 KB Output is correct
15 Correct 36 ms 19064 KB Output is correct
16 Correct 28 ms 21136 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 18124 KB Output is correct
2 Correct 2 ms 6192 KB Output is correct
3 Correct 23 ms 17800 KB Output is correct
4 Correct 34 ms 19600 KB Output is correct
5 Correct 31 ms 19552 KB Output is correct
6 Correct 26 ms 18264 KB Output is correct
7 Correct 30 ms 18032 KB Output is correct
8 Correct 32 ms 18836 KB Output is correct
9 Correct 37 ms 18836 KB Output is correct
10 Correct 33 ms 18504 KB Output is correct
11 Correct 34 ms 18468 KB Output is correct
12 Correct 33 ms 18500 KB Output is correct
13 Correct 31 ms 18540 KB Output is correct
14 Correct 36 ms 19160 KB Output is correct
15 Correct 43 ms 18824 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 18124 KB Output is correct
2 Correct 2 ms 6192 KB Output is correct
3 Correct 23 ms 17800 KB Output is correct
4 Correct 34 ms 19600 KB Output is correct
5 Correct 31 ms 19552 KB Output is correct
6 Correct 26 ms 18264 KB Output is correct
7 Correct 30 ms 18032 KB Output is correct
8 Correct 32 ms 18836 KB Output is correct
9 Correct 37 ms 18836 KB Output is correct
10 Correct 33 ms 18504 KB Output is correct
11 Correct 34 ms 18468 KB Output is correct
12 Correct 33 ms 18500 KB Output is correct
13 Correct 31 ms 18540 KB Output is correct
14 Correct 36 ms 19160 KB Output is correct
15 Correct 43 ms 18824 KB Output is correct
16 Correct 26 ms 16500 KB Output is correct
17 Correct 22 ms 16524 KB Output is correct
18 Correct 23 ms 16524 KB Output is correct
19 Correct 31 ms 16632 KB Output is correct
20 Correct 28 ms 17264 KB Output is correct
21 Correct 26 ms 17028 KB Output is correct
22 Correct 32 ms 19080 KB Output is correct
23 Correct 25 ms 16776 KB Output is correct
24 Correct 28 ms 16880 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6436 KB Output is correct
2 Correct 2 ms 6192 KB Output is correct
3 Correct 2 ms 6444 KB Output is correct
4 Execution timed out 3060 ms 5980 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 16436 KB Output is correct
2 Execution timed out 3067 ms 8028 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 16516 KB Output is correct
2 Execution timed out 3033 ms 8024 KB Time limit exceeded
3 Halted 0 ms 0 KB -