Submission #959814

#	Time	Username	Problem	Language	Result	Execution time	Memory
959814		andrei_boaca	Stray Cat (JOI20_stray)	C++17	100 / 100	57 ms	19936 KiB

Anthony

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

using namespace std;
typedef pair<int,int> pii;
namespace
{
    pii a={0,0},b={0,1},c={1,1};
    vector<pii> vec={b,c,b,b,b,a};
    map<pii,int> myind;
    int INF=1e9;
    vector<int> muchii[20005];
    vector<pii> g;
    int dist[20005];
    int par[20005];
    int n,m;
    void bfs()
    {
        for(int i=0;i<n;i++)
            dist[i]=INF;
        dist[0]=0;
        queue<int> coada;
        coada.push(0);
        while(!coada.empty())
        {
            int nod=coada.front();
            coada.pop();
            for(int i:muchii[nod])
                if(dist[i]>dist[nod]+1)
                {
                    dist[i]=dist[nod]+1;
                    coada.push(i);
                }
        }
    }
    int garbage(int x)
    {
        if(x%3==0)
            return 0;
        if(x%3==1)
            return 1;
        return 2;
    }
    vector<int> subtask14()
    {
        vector<int> sol;
        for(int i=0;i<m;i++)
        {
            int a=g[i].first,b=g[i].second;
            if(dist[a]>dist[b])
                swap(a,b);
            int val=garbage(dist[a]);
            sol.push_back(val);
        }
        return sol;
    }
    vector<int> sol;
    void dfs(int nod)
    {
        if(nod==0)
        {
            for(int i:muchii[nod])
                if(i!=par[nod])
                {
                    par[i]=nod;
                    int ind=myind[{nod,i}];
                    sol[ind]=0;
                    dfs(i);
                }
            return;
        }
        if(muchii[nod].size()>=3)
        {
            int c=sol[myind[{nod,par[nod]}]];
            c=1-c;
            for(int i:muchii[nod])
                if(i!=par[nod])
                {
                    par[i]=nod;
                    int ind=myind[{nod,i}];
                    sol[ind]=c;
                    dfs(i);
                }
            return;
        }
        int cul=sol[myind[{nod,par[nod]}]];
        int poz;
        if(cul==0)
            poz=5;
        else
            poz=1;
        while(true)
        {
            if(muchii[nod].size()>2)
            {
                dfs(nod);
                break;
            }
            if(muchii[nod].size()==1)
                break;
            int nxt=(muchii[nod][0]^muchii[nod][1]^par[nod]);
            int c=sol[myind[{nod,par[nod]}]];
            c=(vec[poz].first^vec[poz].second^c);
            sol[myind[{nod,nxt}]]=c;
            par[nxt]=nod;
            poz++;
            poz%=6;
            nod=nxt;
        }
    }
}
/// a={0,0}, b={0,1}, c={1,1}
vector<int> Mark(int N, int M, int A, int B,vector<int> U, vector<int> V)
{
    n=N;
    m=M;
    for(int i=0;i<m;i++)
    {
        int a=U[i],b=V[i];
        muchii[a].push_back(b);
        muchii[b].push_back(a);
        g.push_back({a,b});
        myind[{a,b}]=myind[{b,a}]=i;
    }
    bfs();
    if(B==0)
    {
        vector<int> sol=subtask14();
        return sol;
    }
    par[0]=-1;
    sol.resize(m);
    dfs(0);
    return sol;
}

Catherine

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

using namespace std;
typedef pair<int,int> pii;
namespace
{
    bool penal;
    int sure, prv;
    pii aa={0,0},bb={0,1},cc={1,1};
    vector<vector<pii>> bad={{aa,bb,cc},{cc,bb,bb},{bb,bb,bb,aa},{bb,bb,aa,bb},{bb,aa,bb,cc},{bb,cc,bb,bb}};
    vector<pii> v;
    pii gettype(vector<int> y)
    {
        if(y[0]==2)
            return aa;
        if(y[1]==2)
            return cc;
        return bb;
    }
}

void Init(int A, int B)
{
    if(B==0)
        penal=1;
    prv=-1;
    sure=0;
}
int Move(vector<int> y)
{
    if(penal)
    {
        int cnt=0;
        for(int i=0;i<3;i++)
            if(y[i]!=0)
                cnt++;
        if(cnt==1)
        {
            for(int i=0;i<3;i++)
                if(y[i]>0)
                    return i;
        }
        if(y[0]>0&&y[1]>0)
            return 0;
        if(y[0]>0&&y[2]>0)
            return 2;
        return 1;
    }
    if(prv==-1)
    {
        if(y[0]+y[1]!=2)
        {
            sure=1;
            if(y[0]==1)
            {
                prv=0;
                return 0;
            }
            else
            {
                prv=1;
                return 1;
            }
        }
        pii x=gettype(y);
        v.push_back(x);
        prv=x.first;
        return x.first;
    }
    if(sure==0)
    {
        if(y[0]+y[1]>=2)
        {
            sure=1;
            y[prv]++;
            if(y[prv]==1)
                return -1;
            else
            {
                prv=1-prv;
                return prv;
            }
        }
        if(y[0]+y[1]==0)
        {
            sure=1;
            return -1;
        }
        y[prv]++;
        pii x=gettype(y);
        v.push_back(x);
        for(auto j:bad)
        {
            if(j==v)
            {
                sure=1;
                return -1;
            }
        }
        y[prv]--;
        if(v.size()>=4)
            sure=1;
        if(y[0]>=1)
        {
            prv=0;
            return 0;
        }
        if(y[1]>=1)
        {
            prv=1;
            return 1;
        }
    }
    if(sure==1)
    {
        if(y[0]>=1&&y[1]>=1)
        {
            int cul=1-prv;
            prv=cul;
            return cul;
        }
        if(y[0]>=1)
        {
            prv=0;
            return 0;
        }
        if(y[1]>=1)
        {
            prv=1;
            return 1;
        }
    }

}

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:136:1: warning: control reaches end of non-void function [-Wreturn-type]
  136 | }
      | ^

• 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