Submission #375653

#	Time	Username	Problem	Language	Result	Execution time	Memory
375653		Alex_tz307	Game (IOI14_game)	C++17	100 / 100	566 ms	16108 KiB

game

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1505;
int N, p[NMAX], sz[NMAX], cnt[NMAX][NMAX];

int get(int x) {
    if(x == p[x])
        return x;
    return p[x] = get(p[x]);
}

void unite(int u, int v) {
    if(u == v)
        return;
    if(sz[u] < sz[v])
        swap(u, v);
    for(int k = 1; k <= N; ++k)
        cnt[u][k] += cnt[v][k], cnt[k][u] += cnt[v][k];
    cnt[u][v] = cnt[v][u] = 0;
    p[v] = u;
}

void initialize(int n) {
    N = n;
    for(int i = 1; i <= N; ++i) {
        p[i] = i;
        sz[i] = 1;
        for(int j = 1; j <= N; ++j)
            if(i != j)
                cnt[i][j] = 1;
    }
}

int hasEdge(int u, int v) {
    ++u, ++v;
    u = get(u);
    v = get(v);
    if(cnt[u][v] > 1) { /// daca am cnt > 1, pot sa nu le unesc si practic judge-ul nu afla nimic.
        /// Pentru a fi graful conex, trebuie sa unesc u si v, dar eu inca mai am niste variante de muchii cu care le pot uni.
        /// Astfel, judge-ul prin intrebarea asta nu afla nimic sigur, graful putand fi ori conex ori sa nu fie conex(asta stie doar cand ajunge la ultima muchie ce poate uni u si v si afla daca exista sau nu).
        /// E clar de aici ca jocul ce il simulam pentru a avea o strategie sigura de castig
        /// are la baza un graf conex(daca nu ar fi conex, judge-ul ar putea afla mai repede ca nu poate uni 2 
      	/// componente de pe parcurs si ar sti la un pas i < r ca graful nu e conex, deci am pierde).
        /// Prin prisma faptului ca 2 componente de pe parcurs sunt unite doar 
        /// in momentul in care mai exista o unica muchie ce le poate uni,
        /// inductiv, realizam ca judge-ul va afla ca graful este conex doar la intrebarea r,
        /// cand va uni ultimele 2 componente ramase cu singura muchie ramasa ce le poate uni, deci va pierde mereu.
        --cnt[u][v], --cnt[v][u];
        return 0;
    }
    /// Aici pe langa muchiile ce unesc 2 componente mai trasez si alea
    /// ce au capetele in 2 noduri din aceeasi componenta, dar asta nu este obligatoriu
    /// ele fiind irelevante pentru continuitatea jocului in acest punct.
    unite(u, v);
    return 1;
}

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