Submission #923265

#	Time	Username	Problem	Language	Result	Execution time	Memory
923265		huutuan	Stray Cat (JOI20_stray)	C++14	91 / 100	39 ms	17840 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>

using namespace std;

#ifndef sus
#define cerr if (0) cerr
#endif

const int N=2e4+10;

namespace sub1234{
   vector<int> g[N];
   vector<int> ans;
   int dep[N];
   void bfs(){
      memset(dep, -1, sizeof dep);
      queue<int> q;
      q.push(0); dep[0]=0;
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:g[u]){
            if (dep[v]==-1){
               dep[v]=dep[u]+1;
               q.push(v);
            }
         }
      }
   }
   vector<int> solve(int n, int m, vector<int> u, vector<int> v){
      ans.resize(m, -1);
      for (int i=0; i<m; ++i){
         g[u[i]].push_back(v[i]);
         g[v[i]].push_back(u[i]);
      }
      bfs();
      for (int i=0; i<m; ++i){
         ans[i]=min(dep[u[i]], dep[v[i]])%3;
         cerr << u[i] << ' ' << v[i] << ' ' << ans[i] << '\n';
      }
      return ans;
   }
}

namespace sub567{
   string sussy="011001";
   vector<int> path;
   vector<pair<int, int>> g[N];
   vector<int> ans;
   int par_idx[N];
   void dfs(int u, int p){
      pair<int, int> pp={-1, -1};
      for (auto &e:g[u]) if (e.first==p) pp=e;
      if (pp.first!=-1) g[u].erase(find(g[u].begin(), g[u].end(), pp));
      if ((int)g[u].size()==1){
         if (path.empty()) path.push_back(par_idx[u]);
         path.push_back(g[u][0].second);
         par_idx[g[u][0].first]=g[u][0].second;
         dfs(g[u][0].first, u);
      }else{
         if (path.size()){
            int first_edge=path[0]==-1?0:ans[path[0]]^1;
            path.erase(path.begin());
            for (int i=0; i<(int)path.size(); ++i) ans[path[i]]=sussy[(i+first_edge)%6]-'0';
         }
         path.clear();
         for (auto &e:g[u]){
            int v=e.first, i=e.second;
            ans[i]=par_idx[u]==-1?0:ans[par_idx[u]]^1;
            par_idx[v]=i;
            if ((int)g[v].size()==1){
               path.clear();
               path.push_back(par_idx[u]);
            }
            dfs(v, u);
         }
      }
   }
   vector<int> solve(int n, int m, vector<int> u, vector<int> v){
      ans.resize(m);
      par_idx[0]=-1;
      for (int i=0; i<m; ++i){
         g[u[i]].emplace_back(v[i], i);
         g[v[i]].emplace_back(u[i], i);
      }
      dfs(0, -1);
      for (int i=0; i<m; ++i) cerr << u[i] << ' ' << v[i] << ' ' << ans[i] << '\n';
      return ans;
   }
}

vector<int> Mark(int n, int m, int a, int b,
                 vector<int> u, vector<int> v) {
   if (a!=2){
      return sub1234::solve(n, m, u, v);
   }
   return sub567::solve(n, m, u, v);
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>

using namespace std;

#ifndef sus
#define cerr if (0) cerr
#endif

int a, b;

void Init(int A, int B) {
   a=A;
   b=B;
}

vector<pair<int, int>> v;

string sussy="011001";

bool check_sus(){
   if ((int)v.size()<5) return 0;
   string lmao;
   for (int i=5; i>=1; --i){
      if (v.end()[-i].first!=1) return 0;
      lmao.push_back('0'+v.end()[-i].second);
   }
   cerr << "check " << lmao << endl;
   if ((sussy+sussy).find(lmao)!=string::npos){
      cerr << "sus " << lmao << endl;
      return 1;
   }
   return 0;
}

int Move(vector<int> y) {
   if (a!=2){
      if (y[0] && y[1]) return 0;
      if (y[1] && y[2]) return 1;
      if (y[2] && y[0]) return 2;
      for (int i=0; i<3; ++i) if (y[i]) return i;
   }
   if (y[0]+y[1]==1){
      if (y[0]){
         v.emplace_back(1, 0);
         if (check_sus()){
            v.emplace_back(-1, v.back().second);
            return -1;
         }
         return 0;
      }else{
         v.emplace_back(1, 1);
         if (check_sus()){
            v.emplace_back(-1, v.back().second);
            return -1;
         }
         return 1;
      }
   }
   if (v.size()){
      int lst=v.back().second;
      if (y[lst^1]==1){
         v.emplace_back(0, lst^1);
         return lst^1;
      }
      v.emplace_back(-1, lst);
      return -1;
   }
   if (y[0]==1 && y[1]==1){
      v.emplace_back(1, 0);
      v.emplace_back(1, 1);
      return 1;
   }
   if (y[1]==1){
      v.emplace_back(y[0]<=1, 1);
      return 1;
   }
   if (y[0]==1){
      v.emplace_back(y[1]<=1, 0);
      return 0;
   }
   if (y[1]){
      v.emplace_back(0, 1);
      return 1;
   }
   if (y[0]){
      v.emplace_back(0, 0);
      return 0;
   }
   return -1;
}

• 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: 0 / 9