Submission #163430

#	Time	Username	Problem	Language	Result	Execution time	Memory
163430		davitmarg	Game (IOI14_game)	C++17	15 / 100	5 ms	504 KiB

game

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

#ifndef death
#include "game.h"
#endif

const int N = 5003;

int n, msk, sk, dp[(1 << 6) + 10][(1 << 6) + 10], used[(1 << 6) + 10][(1 << 6) + 10], ind[7][7], k;
vector<pair<int, int>> p;

bool connected(int mask)
{
    vector<vector<int>> g(n + 5);
    vector<int> u(n + 5);
    for (int i = 0; i < k; i++)
        if ((1 << i) & mask)
        {
            int a = p[i].first;
            int b = p[i].second;
            g[a].PB(b);
            g[b].PB(a);
        }
    queue<int> q;
    q.push(0);
    u[0] = 1;
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (int i = 0; i < g[v].size(); i++)
        {
            int to = g[v][i];
            if (u[to])
                continue;
            u[to] = 1;
            q.push(to);
        }
    }
    for (int i = 0; i < n; i++)
        if (u[i] == 0)
            return 0;
    return 1;
}

bool norm(int mask, int s)
{
    return (!connected(s) && connected(s | (((1 << k) - 1) ^ mask)));
}

void dfs(int mask, int s)
{
    if (used[mask][s])
        return;
    used[mask][s] = 1;
    if (norm(mask, s) == 0)
        return;
    dp[mask][s] = 1;
    for (int i = 0; i < k; i++)
    {
        if ((1 << i) & mask)
            continue;
        int newmask = mask | (1 << i);
        dfs(newmask, s);
        dfs(newmask, s | (1 << i));
        if (dp[newmask][s] == 0 && dp[newmask][s | (1 << i)] == 0)
        {
            dp[mask][s] = 0;
            break;
        }
    }
}

void initialize(int x)
{
    n = x;
    k = n * (n - 1) / 2;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            ind[i][j] = ind[j][i] = p.size();
            p.PB(MP(i, j));
        }
    for (int mask = 0; mask < (1 << k); mask++)
    {
        dp[(1 << k) - 1][mask] = 1;
        used[(1 << k) - 1][mask] = 1;
    }
    dfs(0, 0);
}

int hasEdge(int u, int v)
{
    int x = ind[u][v];
    msk |= (1 << x);
    if (dp[msk][sk] == 1)
        return 0;
    sk |= (1 << x);
    return 1;
}

#ifdef death

int main()
{
    int N;
    cin >> N;
    initialize(N);
    N = N * (N - 1) / 2;
    while (N--)
    {
        int a, b;
        cin >> a >> b;
        cout << hasEdge(a, b) << endl;
    }
    return 0;
}

#endif

/*


*/

Compilation message (stderr)

game.cpp: In function 'bool connected(int)':
game.cpp:53:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[v].size(); i++)
                         ~~^~~~~~~~~~~~~

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