Submission #382495

#	Time	Username	Problem	Language	Result	Execution time	Memory
382495		davooddkareshki	Game (IOI14_game)	C++17	100 / 100	482 ms	16492 KiB

game

//#include "game.h"
#include<bits/stdc++.h>

typedef long long ll;
typedef long double ld;

using namespace std;

//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

const int inf = 1e9;
const int maxn = 1510;
const int mod = 1e9+7;

int n;
int pors[maxn][maxn], par[maxn], sz[maxn];

int get_par(int v)
{
    if(par[v] == -1) return v;
    return (par[v] = get_par(par[v]));
}

int dsu(int u, int v)
{
    u = get_par(u);
    v = get_par(v);
    if(sz[v] < sz[u]) swap(u,v);

    if(u == v) return 0;

    pors[u][v]++;
    pors[v][u]++;
    if(pors[u][v] == (sz[v] * sz[u]))
    {
        for(int i = 0; i < n; i++)
        {
            if(par[i] == -1 && i != u && i != v)
            {
                pors[v][i] += pors[u][i];
                pors[i][v] += pors[u][i];
            }
        }

        sz[v] += sz[u];
        par[u] = v;
        return 1;
    }
    return 0;
}

void initialize(int N) {
    n = N;
    for(int i = 0; i < maxn; i++)
    {
        par[i] = -1;
        sz[i] = 1;
    }
    memset(pors, 0, sizeof pors);
}

int hasEdge(int u, int v) {
    return dsu(u,v);
}

/*signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    initialize(5);
    cout<< hasEdge(0,1) <<"\n";
    cout<< hasEdge(0,2) <<"\n";
    cout<< hasEdge(0,3) <<"\n";
    cout<< hasEdge(0,4) <<"\n";
    cout<< hasEdge(1,2) <<"\n";
    cout<< hasEdge(1,3) <<"\n";
    cout<< hasEdge(1,4) <<"\n";
    cout<< hasEdge(2,3) <<"\n";
    cout<< hasEdge(2,4) <<"\n";
    cout<< hasEdge(3,4) <<"\n";
}*/

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