Submission #996578

#	Time	Username	Problem	Language	Result	Execution time	Memory
996578		TimDee	Stray Cat (JOI20_stray)	C++17	91 / 100	40 ms	16780 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 

const int N=2e4+5;
vector<pi> adj[N];
int z[N];
int c[N];
int ed[N];

vector<int> ptrn={0,1,1,0,0,0,1,0,0,1,1,1};

void dfs(int u, int p) {
    for(auto&e:adj[u]) {
        int v=e.f, i=e.s;
        if (v==p) continue;
        if (adj[v].size()==2) {
            z[v]=z[u]+1;
            c[v]=ptrn[z[u]%12];
            ed[i]=ptrn[z[u]%12];
        } else {
            z[v]=c[u]*6;
            c[v]=c[u]^1;
            ed[i]=c[u]^1;
        }
        dfs(v,u);
    }
}

vector<int> Mark(int n, int m, int A, int B, vector<int> u, vector<int> v) {

    if (!B) {
        forn(i,m) adj[u[i]].pb({v[i],i}), adj[v[i]].pb({u[i],i});
        queue<int> q; q.push(0);
        vector<int> vis(n); vis[0]=1;
        vector<int> d(n);
        while (q.size()) {
            int u=q.front(); q.pop();
            for(auto&e:adj[u]) {
                int v=e.f, i=e.s;
                if (!z[i]) {
                    z[i] = (d[u]%3)+1;
                }
                if (vis[v]) continue;
                vis[v]=1;
                q.push(v);
                d[v]=d[u]+1;
            }
        }
        vector<int> ans(m);
        forn(i,m) ans[i]=z[i]-1;
        return ans;
    }
    forn(i,m) adj[u[i]].pb({v[i],i}), adj[v[i]].pb({u[i],i});
    z[0]=6; dfs(0,-1);
    vector<int> ans(m);
    forn(i,m) ans[i]=ed[i];
    return ans;

}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 

int fmove=1;
int rdir=0;
int last=-1;
int alt=0;
void Init(int A, int B) {
    if (!B) alt=1;
}

vector<int> ok;
vector<int> ptn={0,1,1,0,0,0,1,0,0,1,1,1};

int Move(vector<int> a) {
    
    if (alt) {
        if (a[0]&&a[2]) return 2;
        if (a[0]&&a[1]) return 0;
        if (a[1]&&a[2]) return 1;
        forn(i,3) if (a[i]) return i;
    }

    if (fmove) {
        fmove=0;
        if (a[0]+a[1] == 1) {
            rdir=1;
            if (a[0]) return last=0;
            if (a[1]) return last=1;
            assert(0);
        }
        if (a[0]+a[1]>2) {
            rdir=1;
            if (a[0]==1) return last=0;
            if (a[1]==1) return last=1;
            assert(0);
        }
        for(int i=1; i>=0; --i) forn(j,a[i]) ok.pb(i);
        forn(i,2) if (a[i]) return last=i;
        assert(0);
    }

    if (rdir) {
        if (!(a[0]+a[1])) return -1;
        assert(a[0]+a[1]);
        if (a[0]+a[1]==1) forn(i,2) if (a[i]) return last=i;
        assert(a[last^1]);
        return last^=1;
    }
    
    if (a[0]+a[1]==0) {
        rdir = 1;
        return -1;
    }
    if (a[0]+a[1] > 1) {
        if (a[0] && a[1]) {
            rdir=1;
            return last^=1;
        }
        rdir=1;
        return -1;
    }

    if (a[0]) {
        ok.pb(0);
    } else {
        ok.pb(1);
    }

    if (ok.size()==6) {
        int kk=0;
        forn(i,12) {
            int z=1;
            forn(j,6) z&=ok[j]==ptn[(i+j)%12];
            kk|=z;
        }
        if (kk) {
            rdir=1;
            return -1;
        }
        rdir=1;
        return last=ok.back();
    }
    return last=ok.back();

}

• 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