Submission #641427

#	Time	Username	Problem	Language	Result	Execution time	Memory
641427		MasterTaster	Game (IOI14_game)	C++14	100 / 100	657 ms	78012 KiB

game

#include <iostream>
#include <set>
#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], n, cnt[1510][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 ru, int rv)
{
    //if (root(u)==root(v)) return;

    if (rnk[ru]<=rnk[rv])
    {
        if (rnk[ru]==rnk[rv]) rnk[rv]++;
        dsu[ru]=rv;
    }
    else
        dsu[rv]=ru;

    int r=root(ru);
    int pr=ru+rv-r;
    ///cout<<ru<<"+"<<rv<<"->"<<r<<endl;
    for (int i=0; i<n; i++) {
        cnt[i][r]+=cnt[i][pr];
        cnt[r][i]+=cnt[i][pr];
    }
}

void initialize(int N) {

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

}

void out()
{
    for (int i=0; i<n; i++) { for (int j=0; j<n; j++) if (i!=j) cout<<cnt[i][j]<<" "; else cout<<-1<<" "; cout<<endl; }
}

int hasEdge(int u, int v) {

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

    if (ru==rv) return 1;

    if (cnt[ru][rv]>1)
    {
        cnt[ru][rv]--;
        cnt[rv][ru]--;
        return 0;
    }
    else
    {
        connect(ru, rv);
        //out();
        return 1;
    }

    /*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: 58 / 58