Submission #241719

#	Time	Username	Problem	Language	Result	Execution time	Memory
241719		Coroian_David	Game (IOI14_game)	C++11	100 / 100	591 ms	25336 KiB

game

#include <bits/stdc++.h>

#include "game.h"

#define MAX_N 1500

using namespace std;
/*
int ap[MAX_N + 1];

int pos[MAX_N + 1][MAX_N + 1];
int p2[MAX_N + 1][MAX_N + 1];
*/
int N;

int comp[MAX_N + 1];
int h[MAX_N + 1];
int dp[MAX_N + 1][MAX_N + 1];

void initialize(int n)
{
    for(int i = 1; i <= n; i ++)
    {
        comp[i] = i;
        h[i] = 1;

        for(int j = 1; j <= n; j ++)
        {
            if(i != j)
                dp[i][j] = 1;
        }
    }

    N = n;
    return;
/*
    for(int i = 1; i <= n; i ++)
    {
        ap[i] = n - 1;

        for(int j = 1; j <= n; j ++)
        {
            if(i != j)
            {
                pos[i][j] = 1;

                p2[i][j] = 1;
            }
        }
    }*/
}
/*
void verif(int a)
{
    int n = N;
    if(ap[a] != 1)
        return;

    //cout << "BAGAM LA " << a << "\n";

    for(int i = 1; i <= n; i ++)
    {
        if(i != a && ap[i] > 0 && pos[a][i] == 1)
        {
          //  cout << "SE COMBINA CU " << i << "\n";

            pos[a][i] = pos[i][a] = 2;
            ap[i] --;
            ap[a] --;

            verif(i);

            return;
        }
    }
}

int viz[MAX_N + 1];

int cr, cnt;

void dfs(int a)
{
    cnt ++;
    viz[a] = cr;
    for(int i = 1; i <= N; i ++)
    {
        if(i != a && p2[i][a] == 1 && viz[i] < cr)
        {
            dfs(i);
        }
    }
}

int brut(int u, int v)
{
    p2[u][v] = p2[v][u] = 0;

    cr ++;
    cnt = 0;
    dfs(u);

    int rez = 0;
    if(cnt < N)
        rez = 1;

    p2[v][u] = p2[u][v] = rez;

    return rez;
}

*/
int getComp(int a)
{
    return (comp[a] = (comp[a] == a ? a : getComp(comp[a])));
}

void uneste(int a, int b)
{
    if(h[a] < h[b])
        swap(a, b);

    comp[b] = a;
    h[a] += (h[a] == h[b]);

    int n = N;
    for(int i = 1; i <= n; i ++)
    {
        int x = getComp(i);

        if(x != a)
        {
            dp[x][a] += dp[x][b];
            dp[x][b] = 0;

            dp[a][x] += dp[b][x];
            dp[b][x] = 0;
        }
    }
}

int hasEdge(int u, int v)
{
    u ++;
    v ++;

    int ca = getComp(u);
    int cb = getComp(v);

    if(ca == cb)
    {
        return 0;
    }

    else
    {
        if(dp[ca][cb] == 1)
        {
            uneste(ca, cb);

            return 1;
        }

        else
        {
            dp[ca][cb] --;
            dp[cb][ca] --;

            return 0;
        }
    }

    return 0;
/*
    int r2 = brut(u, v);

    if(r2 != rez)
    {
        cout << ap[v] << " " << ap[u] << "\n";
        cout << " POS " << pos[u][v] << " " << pos[v][u] << " \n";
        cout << " SUINTEM ACOACOAL L O " << u << " " << v << " " << cnt  << " " << cr << " si trebuie " << r2 << " iese " << rez << "\n";
    }


    assert(r2 == rez);

    return rez;*/
}

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