Submission #592936

#	Time	Username	Problem	Language	Result	Execution time	Memory
592936		Mamedov	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1092 ms	3856 KiB

tournament

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// sub 1-2
struct DSU {
  int components;
  vector<int>par;
  DSU(int n) {
    par.assign(n, -1);
    components = n;
  }
  int Find(int u) {
    if (par[u] < 0) return u;
    else return par[u] = Find(par[u]);
  }
  bool Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u != v) {
      par[u] += par[v];
      par[v] = u;
      --components;
      return true;
    } else {
      return false;
    }
  }
};

int dfs(int node, int N, int R, vi &val, vvi &g) {
  int res = 0;
  for (int to : g[node]) {
    res += dfs(to, N, R, val, g);
    val[node] = max(val[node], val[to]);
  }
  if (node >= N && val[node] == R) ++res;
  return res;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  vvi g(2 * N);
  int nextNode = N - 1;
  DSU dsu(2 * N);
  for (int i = 0; i < C; ++i) {
    int node = 0, pos = 0, root = dsu.Find(node);
    while (pos < S[i]) {
      ++node;
      int newRoot = dsu.Find(node);
      if (newRoot != root) {
        root = newRoot;
        ++pos;
      }
    }
    ++nextNode;
    g[nextNode].eb(root);
    dsu.Union(nextNode, root);
    root = nextNode;
    while (pos < E[i]) {
      ++node;
      root = dsu.Find(node);
      if (root != nextNode) {
        g[nextNode].eb(root);
        dsu.Union(nextNode, root);
        root = nextNode;
        ++pos;
      }
    }
  }
  int best = 0, bestPos = 0;
  for (int i = 0; i < N; ++i) {
    vector<int>val(nextNode + 1, -1);
    for (int j = 0; j < i; ++j) {
      val[j] = K[j];
    }
    val[i] = R;
    for (int j = i; j < N - 1; ++j) {
      val[j + 1] = K[j];
    }
    int cur = dfs(nextNode, N, R, val, g);
    if (cur > best) {
      best = cur;
      bestPos = i;
    }
  }
  return bestPos;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51