Submission #719161

#	Time	Username	Problem	Language	Result	Execution time	Memory
719161		lam	Stray Cat (JOI20_stray)	C++14	100 / 100	53 ms	16600 KiB

Anthony

#include "Anthony.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 2e4 + 10;
const string S = "101001";
int n,m;
bool start; int it;
vector <ii> adj[maxn];
vector <int> type;

void dfs(int x, int p, int val)
{
    int cnt = 0;
    for (ii i:adj[x])
        if (i.ff!=p) cnt++;
    if (cnt>1)
    {
        for (ii i:adj[x])
            if (i.ff!=p)
        {
            start = true;
            type[i.ss] = 1-val;
            dfs(i.ff,x,1-val);
        }
    }
    else if (cnt==1)
    {
        if (start)
        {
            start = false;
            if (val==-1||val==1) it = 0;
            else it = 2;
        }
        for (ii i:adj[x])
            if (i.ff!=p)
        {
            type[i.ss] = (S[it]-'0');
            it=(it+1)%6;
            dfs(i.ff,x,type[i.ss]);
        }
    }
}

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
    n=N; m=M;
    type.assign(m,0);
    for (int i=0; i<n; i++) adj[i].clear();
    for (int i=0; i<m; i++)
    {
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    if (A>2)
    {
        queue<int> q;
        vector <int> d(n,-1);
        d[0] = 0; q.push(0);
        while (!q.empty())
        {
            int u=q.front(); q.pop();
            for (ii v:adj[u])
                if (d[v.ff]==-1)
            {
                d[v.ff] = d[u]+1;
                q.push(v.ff);
            }
        }
//        for (int i=0; i<n; i++) cerr<<i<<" : "<<d[i]<<endl;
        for (int i=0; i<m; i++)
        {
            int u=U[i]; int v=V[i];
            if (d[u]>d[v]) swap(u,v);
            type[i] = (d[v]%3);
            if (d[u]==d[v]) type[i] = (type[i]+1)%3;
        }
        return type;
    }
    start = true;
    dfs(0,-1,1);
//    for (int i=0; i<m; i++) cerr<<type[i]<<' '; cerr<<endl;
    return type;
}

Catherine

#include "Catherine.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

bool sub1;
bool _starts, _lost;
int val;
string s;

void Init(int A, int B) {
    if (A>2) sub1=1;
    else
    {
        s="";
        sub1=0;
        _starts = 1;
        _lost = 1;
    }
}

int Move(std::vector<int> y) {
//    cerr<<"? "<<_starts<<' '<<_lost<<' '<<val<<endl;
    if (sub1)
    {
        if ((y[0]>0&&y[1]>0)) return 0;
        if ((y[2]>0&&y[1]>0)) return 1;
        if ((y[0]>0&&y[2]>0)) return 2;
        if (y[0]) return 0;
        if (y[1]) return 1;
        if (y[2]) return 2;
        assert(false);
        return -1;
    }
    else
    {
        if (!_starts&&!_lost)
        {
            if (y[0]+y[1]==1)
            {
                if (y[0]) return val=0;
                else return val=1;
            }
            else if (y[0]+y[1]>1) return val=1-val;
            else return -1;
        }
        if (_starts)
        {
            _starts = false;
            if (y[0]+y[1]==2)
            {
                if (y[0]==2)
                {
                    s+="00";
                    return val=0;
                }
                else if (y[1]==2)
                {
                    s+="11";
                    return val=1;
                }
                else
                {
                    s+="01";
                    return val=1;
                }
            }
            else
            {
                _lost = false;
                if (y[0]==1) return val=0;
                else if (y[1]==1) return val=1;
                else
                {
                    assert(false);
                    return -1;
                }
            }
        }
        if (_lost)
        {
            if (y[0]+y[1]>1)
            {
                if (y[0]==0||y[1]==0)
                {
//                    cerr<<y[0]<<" & "<<y[1]<<endl;
                    _lost = false;
//                    cerr<<val<<" : "<<_starts<<' '<<_lost<<endl;
                    return -1;
                }
                _lost = false;
                return val = 1-val;
            }
            else if (y[0]+y[1]==0)
            {
                _lost = false;
                return -1;
            }
            else
            {
                if (y[0]) s+='0';
                else s+='1';
                if (s.length()==5)
                {
                    if (s=="10100"||s=="01001"||s=="10011"||s=="00110"||s=="01101"||s=="11010")
                    {
                        s="";
                        _lost = false;
                        return -1;
                    }
                    else
                    {
                        s="";
                        _lost = false;
                        if (y[0]) return val=0;
                        else return val=1;
                    }
                }
                else if (y[0]) return val=0;
                else return val=1;
            }
        }
    }
}

Compilation message (stderr)

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

• 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