Submission #774179

#	Time	Username	Problem	Language	Result	Execution time	Memory
774179		danikoynov	Game (IOI14_game)	C++14	100 / 100	999 ms	36708 KiB

game

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

using namespace std;

const int maxn = 1510;
int n;

int  used[maxn], in_st[maxn * maxn], in_mst[maxn * maxn];
vector < int > st, mst;
mt19937 rng;

void random_shuffle()
{

    for (int i = 0; i < st.size(); i ++)
    {
        int idx = rng() % (int)(st.size());
        swap(st[i], st[idx]);
    }
}

int par[maxn];
int find_leader(int v)
{
    if (v == par[v])
        return v;
    return (par[v] = find_leader(par[v]));
}

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

bitset < maxn > nb[maxn];

void initialize(int N)
{
    n = N;
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++)
        {
            if (i != j)
            {
                nb[i][j] = nb[j][i] = 1;

                st.push_back(i * n + j), in_st[i * n + j] = 1;
            }
        }

    for (int i = 0; i < n; i ++)
        par[i] = i;
    random_shuffle();
    for (int edge : st)
    {
        int v = edge / n, u = edge % n;
        if (unite(v, u))
        {
            ///cout << v << " : " << u << endl;
            in_st[edge] = 0;
            in_mst[edge] = 1;
            mst.push_back(edge);
        }
    }
    random_shuffle();


}
vector < int > adj[maxn];
void dfs(int v, int cnt)
{
    used[v] = cnt;
    for (int u : adj[v])
    {
        if (!used[u])
            dfs(u, cnt);
    }
}

void rem(int v, int u)
{
    int pt = 0;
    while(adj[v][pt] != u)
        pt ++;
    adj[v].erase(adj[v].begin() + pt);
}


int cnt = 0;
int hasEdge(int u, int v)
{
    cnt ++;
    //cout << "----------------" << endl;
    if (u > v)
        swap(u, v);
    int hs = u * n + v;
    if (!in_mst[hs])
    {
        nb[u][v] = nb[v][u] = 0;
        in_st[hs] =0;
        return 0;
    }
    for (int i = 0; i < n; i ++)
        adj[i].clear(), used[i] = 0;


    for (int edge : mst)
    {
        if (edge == hs)
            continue;
        ///cout << edge / n << " " << edge % n << endl;
        adj[edge / n].push_back(edge % n);
        adj[edge % n].push_back(edge / n);
    }


    dfs(0, 1);
    for (int i = 0; i < n; i ++)
        if (used[i] == 0)
        {
            dfs(i, 2);
            break;
        }

    if (n * (n - 1) / 2 - cnt > n * 20)
    {
        bitset < maxn > tk;
        for (int i = 0; i < n; i ++)
        {
            if (used[i] == 1)
                tk[i] = 1;
        }


        nb[hs / n][hs % n] = nb[hs % n][hs / n] = 0;
        for (int i = 0; i < n; i ++)
        {
            if (used[i] == 2)
            {
                bitset < maxn > cur = (nb[i] & tk);
                if (cur.count() > 0)
                {
                    int v = i, u = cur._Find_first();
                    ///cout << v << " : " << u << endl;
                    if (v > u)
                        swap(v, u);
                    in_mst[v * n + u] = 1;
                    mst.push_back(v * n + u);
                    int pt = 0;
                    while(mst[pt] != hs)
                        pt ++;
                    in_mst[hs] = 0;
                    in_st[v * n + u] = 0;
                    mst.erase(mst.begin() + pt);
                    return 0;
                }
            }
        }
        nb[hs / n][hs % n] = nb[hs % n][hs / n] = 1;
        return 1;
    }
    else
    {
    vector < int > new_st;
    for (int cur: st)
    {
        if (in_st[cur])
            new_st.push_back(cur);
    }
    st = new_st;
        for (int edge : st)
        {
            if (edge == hs)
                continue;
            if (used[edge / n] != used[edge % n])
            {
                ///cout << "replace " << edge / n << " " << edge % n << endl;
                in_st[hs] = 0;
                in_mst[edge] = 1;
                mst.push_back(edge);
                in_mst[hs] = 0;
                int pt = 0;
                while(mst[pt] != hs)
                    pt ++;
                mst.erase(mst.begin() + pt);
                in_st[edge] = 0;

                return 0;
            }
        }
    }
    return 1;
}

Compilation message (stderr)

game.cpp: In function 'void random_shuffle()':
game.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < st.size(); i ++)
      |                     ~~^~~~~~~~~~~

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