Submission #419008

#	Time	Username	Problem	Language	Result	Execution time	Memory
419008		MasterTaster	Game (IOI14_game)	C++14	42 / 100	1090 ms	6532 KiB

game

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

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second

using namespace std;

int dsu[1510], rnk[1510];
set<pii> svi;

int root(int u)
{
    while (u!=dsu[u])
    {
        dsu[u]=dsu[dsu[u]];
        u=dsu[u];
    }
    return u;
}

void connect(int u, int v)
{
    //if (root(u)==root(v)) return;

    if (rnk[root(u)]<=rnk[root(v)])
    {
        if (rnk[root(u)]==rnk[root(v)]) rnk[root(v)]++;
        dsu[root(u)]=root(v);
    }
    else
        dsu[root(v)]=root(u);
}

void initialize(int n) {

    for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (i<j) svi.insert({i, j});
    for (int i=0; i<n; i++) { dsu[i]=i; rnk[i]=1; }

}

int hasEdge(int u, int v) {

    if (u>v) swap(u, v);
    int ru, rv; ru=root(u); rv=root(v);

    svi.erase({u, v});

    bool moze=true;
    for (auto par:svi)
    {
        int a, b; a=par.xx; b=par.yy;
        //cout<<a<<" "<<b<<" "<<root(a)<<" "<<root(b)<<" "<<ru<<" "<<rv<<endl;
        if ((root(a)==ru && root(b)==rv) || (root(a)==rv && root(b)==ru)) { moze=false; break; }
    }

    if (!moze) return 0;

    connect(u, v);
    return 1;
}

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