oj.uz

답안 #337341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
337341 2020-12-19T22:32:14 Z acmpanda 게임 (IOI14_game) C++14
15 / 100
 1 ms 492 KB 
#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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Incorrect 1 ms 364 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Incorrect 1 ms 384 KB Output isn't correct
26 Halted 0 ms 0 KB -