Submission #337341

#	Time	Username	Problem	Language	Result	Execution time	Memory
337341		acmpanda	Game (IOI14_game)	C++14	15 / 100	1 ms	492 KiB

game

#include "game.h"
#include "vector"
#include <iostream>

#define DEBUG false

using namespace std;

vector<vector<int> > edges;
vector<int> blob;
vector<int> blobSize;

int N;

void initialize(int n) {
    N = n;
    edges.clear();
    edges.resize(n, vector<int>( n, 0));

    blob.resize(n);
    blobSize.resize(n);

    for (int i = 0; i < n; i++) {
        blob[i] = i;
        blobSize[i] = 1;
    }
}

void printBlobs() {
    for (int i = 0; i < N; i++) {
        cout << "Vertex: " << i << " in " << blob[i] << " of size " << blobSize[blob[i]] << endl;
    }
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (edges[i][j] >= 0) {
                cout << "Edges [" << i << " : " << j << " ] - " << edges[i][j] << endl;
            }
        }
    }
}
/* Merging the blobs means that in the blob array, you change all the j-entries to i's. 
   Then you replace size[i] with size[i] + size[j]. Then for each other blob k, you replace e[i][k] with e[i][k] + e[j][k] 
   (and same with e[k][i]). (What happens to no-longer-existing blobs in the e array should be irrelevant, since they're never 
   going to come up in the blob array.)
*/
void mergeBlobs(int u, int v) {
    int toBlob = blob[u]; 
    int mergeBlob = blob[v];

    blob[v] = toBlob;
    blobSize[toBlob] += blobSize[mergeBlob];

    edges[mergeBlob][toBlob] = -1;
    edges[toBlob][mergeBlob] = -1;

    for (int k = 0; k < N; k++) {
        if (k == toBlob) continue;

        edges[toBlob][k] += edges[mergeBlob][k];
        edges[k][toBlob] += edges[k][mergeBlob];

        
        edges[mergeBlob][k] = -1;
        edges[k][mergeBlob] = -1;
    }
}

/* 
    If e[i][j] <= size[i]*size[j] - 2 (meaning this isn't the last edge between them to be queried), then you answer "no," and 
    add 1 to e[i][j] (and e[j][i]). 
    If e[i][j] = size[i]*size[j] - 1 (meaning this is the last edge between them to be queried), 
    then you answer "yes" and merge the blobs. 
*/

int hasEdge(int u, int v) {
    
    int uBlob, vBlob;

    uBlob = blob[u];
    vBlob = blob[v];

    if (DEBUG) {
        printBlobs();
        cout << u << ", " << v << ": " << edges[uBlob][vBlob] << ", " << blobSize[uBlob]*blobSize[vBlob] << endl;
    }

    if (edges[uBlob][vBlob] <= blobSize[uBlob]*blobSize[vBlob] - 2) {
        edges[uBlob][vBlob] += 1;
        edges[vBlob][uBlob] += 1;
        return 0;
    } else {
        mergeBlobs (u, v);
        return 1;
    }
}

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