Submission #162116

#	Time	Username	Problem	Language	Result	Execution time	Memory
162116		ioane	Game (IOI14_game)	C++14	100 / 100	612 ms	25408 KiB

game

#include "game.h"
#include<bits/stdc++.h>
#define LL int
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define I insert
#define Max(a,b) ((b<a)?a:b)
#define Min(a,b) ((a<b)?a:b)

const LL N = 1503, mod = 1000000007;

using namespace std;

LL n, m, i, j, k, l, r, t, ans;
LL fix[N], a[N][N];
vector < LL > g[N];

void initialize ( LL nn ){
    n = nn;
    for ( LL i = 0; i < n; ++i ){
        fix[i] = i;
        g[i].PB(i);
    }
}

LL hasEdge ( LL u, LL v ){
    LL x = fix[u];
    LL y = fix[v];

    if ( g[x].size() < g[y].size() ) swap ( x, y );


    if ( a[x][y] + 1 != g[x].size() * g[y].size() ){
        a[x][y]++;
        a[y][x]++;
        return 0;
    }
    
    for ( LL i = 0; i < g[y].size(); ++i ){
        g[x].PB(g[y][i]);
        fix[g[y][i]] = x;
    }

    g[y].clear();

    for ( LL i = 0; i < n; ++i ){
        a[x][i] += a[y][i];
        a[i][x] += a[i][y];
    }

    return 1;
}

//      IIIIIIIII      OOOOO             A          NN        N    EEEEEEEEEE
//          I         O     O           A A         N N       N    E
//          I        O       O         A   A        N  N      N    E
//          I        O       O        A     A       N   N     N    E
//          I        O       O       AAAAAAAAA      N    N    N    EEEEEEEE
//          I        O       O      A         A     N     N   N    E
//          I        O       O     A           A    N      N  N    E
//          I         O     O     A             A   N       N N    E
//      IIIIIIIII      OOOOO     A               A  N        NN    EEEEEEEEEE ___ KAPANADZE

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:35:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if ( a[x][y] + 1 != g[x].size() * g[y].size() ){
          ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:41:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for ( LL i = 0; i < g[y].size(); ++i ){
                     ~~^~~~~~~~~~~~~

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