Submission #1063520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063520		Andrey	Stray Cat (JOI20_stray)	C++14	100 / 100	39 ms	21636 KiB

Anthony

#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++;
        }
    }
    int p;
    if(br != 1) {
        usl = {d,d%2};   
    }
    else {
        for(int i = 0; i < 6; i++) {
            if((usl.first == -1 || bruhseq[(i+(d-usl.first))%6]%2 == usl.second)) {
                p = i;
                break;
            }
        }
    }
    for(pair<int,int> v: haha[a]) {
        if(v.first != t) {
            if(br == 1 && haha[v.first].size() != 2) {
                if(bruhseq[p]%2 != d%2) {
                    dfs(v.first,a,d+2,usl);
                }
                else {
                    dfs(v.first,a,d+1,usl);
                }
            }
            else {
                dfs(v.first,a,d+1,usl);
            }
            x = dp[v.first];
        }
    }
    if(br == 1) {
        if(x == -1) {
            x = p-1;
        }
        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});
        /*for(int i = 0; i < troll.size(); i++) {
            cout << troll[i] << " ";
        }
        cout << endl;*/
        return troll;
    }
}

Catherine

#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] == 2) {
                    wow.push_back(0);
                    wow.push_back(0);
                    return 0;
                }
                else if(haha[1] == 2) {
                    wow.push_back(1);
                    wow.push_back(1);
                    return 1;
                }
                else {
                    wow.push_back(1);
                    wow.push_back(0);
                    return 0;
                }
            }
            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() == 4) {
                    if(haha[0] > 0) {
                        wow.push_back(0);
                    }
                    else {
                        wow.push_back(1);
                    }
                    for(int i = 0; i < 6; i++) {
                        bool bubu = true;
                        for(int j = i; j < i+5; j++) {
                            if(wow[j-i] != seq[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 (stderr)

Anthony.cpp: In function 'void dfs(int, int, int, std::pair<int, int>)':
Anthony.cpp:32:29: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   32 |                 if(bruhseq[p]%2 != d%2) {
      |                    ~~~~~~~~~^

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:139:29: warning: division by zero [-Wdiv-by-zero]
  139 |                     return 1/0;
      |                            ~^~
Catherine.cpp:152:1: warning: control reaches end of non-void function [-Wreturn-type]
  152 | }
      | ^

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9