Submission #813701

#	Time	Username	Problem	Language	Result	Execution time	Memory
813701		Pikachu	Game (IOI14_game)	C++17	0 / 100	1 ms	372 KiB

game

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

using namespace std;

const int n = 4, m = n * (n - 1) / 2;
typedef array<int,m> state;
state tmp;
map<state,int> mp[m];
pair<int,int> edge[m];

int par[n];

int findpar(int x)
{
    return par[x] != -1 ? par[x] = findpar(par[x]) : x;
}

bool unite(int u, int v)
{
    u = findpar(u);
    v = findpar(v);
    if (u != v) return par[u] = v, true;
    return false;
}

bool check(const state &st)
{
    memset(par, -1, sizeof par);
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (st[i]) cnt += unite(edge[i].first, edge[i].second);
    }
    return cnt == n - 1;
}

int call(state st, int count)
{
    if (mp[count].count(st)) return mp[count][st];
    int &d = mp[count][st] = 2;
    if (count == m - 1) {
        for (int i = 0; i < m; i++) {
            if (st[i] == 2) {
                state tmp1 = st;
                state tmp2 = st;
                tmp1[i] = 0;
                tmp2[i] = 1;
                if (check(tmp1) == check(tmp2)) {
                    return d = 1;
                }
            }
        }
        return d = 2;
    }
    for (int i = 0; i < m; i++) {
        if (st[i] == 2) {
            state tmp1 = st;
            state tmp2 = st;
            tmp1[i] = 0;
            tmp2[i] = 1;
            if (call(tmp1, count + 1) != 2 && call(tmp2, count + 1) != 2) {
                return d = 1;
            }
        }
    }
    return d;
}

void initialize(int n) 
{
    assert(::n == n);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            edge[cnt++] = {i, j};
        }
    }
    for (int i = 0; i < m; i++) tmp[i] = 2;
}

int cnt = 0;

int hasEdge(int u, int v) 
{
    if (u > v) swap(u, v);
    int id = 0;
    while (edge[id] != make_pair(u, v)) id++;
    if (tmp[id] != 2) return tmp[id];
    cnt++;
    tmp[id] = 0;
    if (call(tmp, cnt) == 2) return 0;
    tmp[id] = 1;
    return 1;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 27
• Subtask 3: 0 / 58