Submission #577619

#	Time	Username	Problem	Language	Result	Execution time	Memory
577619		Mazaalai	Game (IOI14_game)	C++17	0 / 100	1 ms	348 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define lb lower_bound
#define pb push_back
#define LINE "------------\n"
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
const int N = 1500;
vector <int> paths[N];
int n;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int pos[N][N];
void initialize(int _n) {
    n = _n;
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
        if (i == j) continue;
        paths[i].pb(j);
    }
    for (int i = 0; i < n; i++)
        shuffle(ALL(paths[i]), rng);
    for (int i = 0; i < n; i++)
    for (int j = 0; j < n-1; j++) 
        pos[i][paths[i][j]] = j;

    // for (int i = 0; i < n; i++) {
    //     cout << i << ": ";
    //     for (auto el : paths[i]) cout << el << ' '; cout << '\n';
    // }
}
int par[N];
int find(int a) {
    return par[a] = (par[a] == a ? a : find(par[a]));
}
bool merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return 0;
    par[b] = a;
    return 1;
}
vector <PII> must;
int hasEdge(int u, int v) {
    // cout << LINE;
    if (paths[u].size() == 1 || paths[v].size() == 1) {
        must.pb({u, v});
        {
            int x = paths[u].size();
            int y = pos[u][v];
            if (x != y) {
                swap(paths[u][y], paths[u][x-1]);
                pos[u][y] = y;
            }
            paths[u].pop_back();
        }
        {
            int x = paths[v].size();
            int y = pos[v][u];
            if (x != y) {
                swap(paths[v][y], paths[v][x-1]);
                pos[v][y] = y;
            }
            paths[v].pop_back();
        }
        return 1;
    }
    int disjoint = n;
    iota(par, par+n, 0);
    {
        int x = paths[u].size();
        int y = pos[u][v];
        if (x != y) {
            swap(paths[u][y], paths[u][x-1]);
            pos[u][y] = y;
        }
        paths[u].pop_back();
    }
    {
        int x = paths[v].size();
        int y = pos[v][u];
        if (x != y) {
            swap(paths[v][y], paths[v][x-1]);
            pos[v][y] = y;
        }
        paths[v].pop_back();
    }
    for (auto [a, b] : must) {
        // cout << "must: " << a << ' ' << b << '\n';
        disjoint -= merge(a, b);
    }
    // cout << u << ' ' << v << '\n';
    // for (int i = 0; i < n; i++) {
    //     cout << i << ": ";
    //     for (auto el : paths[i]) cout << el << ' '; cout << '\n';
    // }
    for (int i = 0; i < n; i++) {
        if (paths[i].size() > 10)
            for (int j = 0; j < 10 && disjoint > 1; j++) {
                int x = paths[i][rng() % paths[i].size()];
                disjoint -= merge(i, x);
            }
        else
            for (int j = 0; j < paths[i].size() && disjoint > 1; j++) {
                int x = merge(i, paths[i][j]);
                // cout << "CHECK: " << i << " " << paths[i][j] << ' ' << x << '\n';
                disjoint -= x;
            }
    }
    // cout << disjoint << '\n';
    // cout << '\n';
    if (disjoint == 1) return 0;
    must.pb({u, v});
    return 1;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:104:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int j = 0; j < paths[i].size() && disjoint > 1; j++) {
      |                             ~~^~~~~~~~~~~~~~~~~

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