Submission #531232

#	Time	Username	Problem	Language	Result	Execution time	Memory
531232		79brue	길고양이 (JOI20_stray)	C++14	100 / 100	54 ms	17012 KiB

Anthony

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

using namespace std;

typedef long long ll;

namespace {
    int n, m, a, b;
    vector<pair<int, int> > link[20002];
    vector<int> ans;
    int dist[20002];
    int col[20002], road[20002];

    void bfs(){
        queue<pair<int, int> > que;
        dist[0] = 1;
        que.push(make_pair(0, 1));
        while(!que.empty()){
            pair<int, int> tmp = que.front(); que.pop();
            int x = tmp.first, d = tmp.second;
            dist[x] = d;

            for(auto y: link[x]){
                if(dist[y.first]) continue;
                dist[y.first] = d+1;
                que.push(make_pair(y.first, d+1));
            }
        }
    }

    const int pattern[] = {0, 0, 1, 0, 1, 1};
    void dfs(int x, int par = -1, int cnt = 0){
        if(x==0){
            for(auto y: link[x]){
                col[y.second] = pattern[cnt%6];
                road[y.first] = y.second;
                dfs(y.first, x, (cnt+1)%6);
            }
            return;
        }

        if((int)link[x].size() == 1) return;
        if((int)link[x].size() == 2){
            for(auto y: link[x]){
                if(y.first == par) continue;
                col[y.second] = pattern[cnt];
                road[y.first] = y.second;
                dfs(y.first, x, (cnt+1)%6);
            }
            return;
        }

        if(col[road[x]]) cnt = 1;
        else cnt = 3;
        for(auto y: link[x]){
            if(par == y.first) continue;
            col[y.second] = !col[road[x]];
            road[y.first] = y.second;
            dfs(y.first, x, cnt);
        }
    }
}

vector<int> Mark(int N, int M, int A, int B, vector<int> U, vector<int> V) {
    n = N, m = M, a = A, b = B;
    for(int i=0; i<m; i++) link[U[i]].push_back(make_pair(V[i], i)), link[V[i]].push_back(make_pair(U[i], i));

    if(A >= 3){
        bfs();
        for(int i=0; i<m; i++){
            ans.push_back((min(dist[U[i]], dist[V[i]]) + 2) % 3);
        }
        return ans;
    }
    else{
        ans.resize(m);
        dfs(0);
        return vector<int> (col, col+m);
    }
}

Catherine

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

using namespace std;

namespace {
    int A, B;

    int pattern[] = {1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0};
    bool strange = 1;
    int cnt = 0;
    int prv = -1;
    vector<int> vb;
}

void Init(int A, int B) {
    ::A = A;
    ::B = B;
    prv = -1, cnt = 0, strange = 1;
}

int Move(vector<int> y){
    if(A >= 3){
        vector<int> lVec;
        for(int i=0; i<A; i++) for(int j=0; j<y[i]; j++) lVec.push_back(i);
        y = lVec;
        int MIN = *min_element(y.begin(), y.end());
        int MAX = *max_element(y.begin(), y.end());
        if(MIN==MAX) return MIN;
        return MAX==1 ? 0 : MIN==1 ? 1 : 2;
    }

    int c0 = y[0], c1 = y[1];
    cnt++;
    if(cnt > 6) strange = 0;

    if(!strange){
        if(!c0) return prv=1;
        if(!c1) return prv=0;

        if(prv == 0) c0++;
        if(prv == 1) c1++;
        if(c0 == 1) return prv=0;
        if(c1 == 1) return prv=1;
    }

    if(prv == 0) c0++;
    if(prv == 1) c1++;

    if(prv == -1){
        if(c0+c1==1){
            strange = 0;
            if(c0) return prv=0;
            return prv=1;
        }
        if(c0+c1>2){
            strange = 0;
            if(c0==1) return prv=0;
            if(c1==1) return prv=1;
        }

        if(c0==2){
            vb.push_back(0);
            vb.push_back(0);
            return prv=0;
        }
        else if(c1==2){
            vb.push_back(1);
            vb.push_back(1);
            return prv=1;
        }
        else{
            vb.push_back(0);
            vb.push_back(1);
            return prv=1;
        }
    }

    if(c0+c1>2){
        strange = 0;
        if(c0==1){
            if(prv==0) return -1;
            return prv = 0;
        }
        if(c1==1){
            if(prv==1) return -1;
            return prv=1;
        }
    }

    if(c0+c1==1){
        strange = 0;
        return -1;
    }
    vb.push_back(y[0] ? 0 : 1);

    bool possible = 0;
    for(int i=0; i<6; i++){
        bool diff=0;
        for(int j=0; j<(int)vb.size(); j++){
            if(pattern[i+j] != vb[j]) diff=1;
        }
        if(!diff) possible=1;
    }
    if(!possible){
        strange=0;
        return -1;
    }
    return prv = y[0]?0: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: 9 / 9