Submission #1156021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156021		an22inkle	Game (IOI14_game)	C++17	15 / 100	1 ms	328 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using paira = array<int, 2>;
using ll = long long;


/*
We need to know- 
Each vertices' components - To do this in O(1), we need to implement DSU
The count of "no" edges between components

When will we be merging? Exactly when there are |c_u| * |c_j| - 1 "no" edges between two components

*/

int N = 2;
vector<vector<int>> edges(N, vector<int>(N)); // # of NO edges between components


// dsu stuff
vector<int> parent(N);
vector<int> asize(N, 0);

void new_compo(int x) {
    parent[x] = x;
    asize[x] = 1;
}

int get_compo(int x) {
    if (parent[x] == x) return x;

    return parent[x] = get_compo(parent[x]);
}

void union_compo(int x, int y) {
    x = get_compo(x);
    y = get_compo(y);

    if (x != y) {
        if (asize[x] < asize[y]) swap(x, y);
        parent[y] = x;
        asize[x] += asize[y];
    }
}

void initialize(int n) {
    N = n;
    edges.resize(N);
    for (int i = 0; i < N; i++) {
        edges[i].resize(N);
    };
    parent.resize(N);
    asize.resize(N);

    for (int i = 0; i < N; i++) {
        new_compo(i);
    }
}

int hasEdge(int u, int v) {
    if (u > v) swap(u, v);

    int cu = get_compo(u);
    int cv = get_compo(v);
    if (cu == cv) {
        return 1;
    }
    if (asize[cu] < asize[cv]) swap(cu, cv);
    // cout << u << ' ' << v << '\n';
    // cout <<  cu << ' ' << cv << ' ' << asize[cu] << ' ' <<  asize[cv] << ' ' << edges[cv][cu] << '\n';
    if (edges[cv][cu] == 1LL*asize[cu]*asize[cv] - 1) {
        // We must answer YES now
        // cv chotota
        // chototar parent hobe borota 
        // chotota deleted
        // cv deleted
        union_compo(cu, cv);
        for (int i = 0; i < N; i++) {
            if (i == cu || i == cv) continue;
        
            edges[min(cu, i)][max(cu, i)] += edges[min(cv, i)][max(i, cv)];
            return 1;
        }

    }

    edges[cv][cu]++;
    return 0;
    

}

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