Submission #577626

#	Time	Username	Problem	Language	Result	Execution time	Memory
577626		Mazaalai	Game (IOI14_game)	C++17	42 / 100	1088 ms	5424 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) {

    {
        int x = 0;
        while(paths[u][x] != v) x++;
        swap(paths[u][x], paths[u].back());
        // cout << "REMOVE: " << u << " " << paths[u].back() << '\n';
        paths[u].pop_back();
    }
    {
        int x = 0;
        while(paths[v][x] != u) x++;
        swap(paths[v][x], paths[v].back());
        // cout << "REMOVE: " << v << " " << paths[v].back() << '\n';
        paths[v].pop_back();
    }
    // cout << LINE;
    // cout << u << ' ' << v << '\n';
    // for (int i = 0; i < n; i++) {
    //     cout << i << ": ";
    //     for (auto el : paths[i]) cout << el << ' '; cout << '\n';
    // }
    if (paths[u].size() == 0 || paths[v].size() == 0) {
        must.pb({u, v});
        return 1;
    }
    int disjoint = n;
    iota(par, par+n, 0);
    for (auto [a, b] : must) {
        // cout << "must: " << a << ' ' << b << '\n';
        disjoint -= merge(a, b);
    }
    for (int i = 0; i < n; i++) {
        if (paths[i].size() > 100)
            for (int j = 0; j < 100 && 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:83:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |             for (int j = 0; j < paths[i].size() && disjoint > 1; j++) {
      |                             ~~^~~~~~~~~~~~~~~~~

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