Submission #774080

#	Time	Username	Problem	Language	Result	Execution time	Memory
774080		danikoynov	게임 (IOI14_game)	C++14	42 / 100	1044 ms	4792 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;
void initialize(int N)
{
    n = N;
    for (int i = 0; i < n; i ++)
        for (int j = i + 1; j < n; j ++)
    {
        if (i != j)
        {

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


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



int hasEdge(int u, int v)
{
    //cout << "----------------" << endl;
    if (u > v)
        swap(u, v);
    int hs = u * n + v;
    if (!in_mst[hs])
    {
        in_st[hs] = 0;
        return 0;
    }
    for (int i = 0; i < n; i ++)
        adj[i].clear(), used[i] = 0;
        random_shuffle(mst.begin(), mst.end());
        random_shuffle(st.begin(), st.end());
    vector < int > new_st;
    for (int cur: st)
    {
        if (in_st[cur])
            new_st.push_back(cur);
    }
    st = new_st;
    vector < int > new_mst;
    for (int cur : mst)
    {
        if (in_mst[cur])
            new_mst.push_back(cur);
    }
    mst = new_mst;
    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;
    }


    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;
            in_st[edge] = 0;
            /**st.erase(hs);
            mst.insert(edge);
            st.erase(edge);
            mst.erase(hs);*/
            return 0;
        }
    }

    return 1;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:53:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   53 |     for (int i = 0; i < n; i ++)
      |     ^~~
game.cpp:55:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   55 |         random_shuffle(mst.begin(), mst.end());
      |         ^~~~~~~~~~~~~~

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