제출 #616086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
616086		Mamedov	Simurgh (IOI17_simurgh)	C++17	100 / 100	144 ms	5536 KiB

simurgh

#pragma GCC optimize ("O3")
#include "simurgh.h"
#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());

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

/// helperTree  (construct any tree and find its edge types (royal or not))
/// findDegree  (find degree for each node)
/// binarySearch (find edges connected to leaf nodes using BS)

bool cmp(array<int, 3>er1, array<int, 3>er2) {
  if (er1[0] * er2[1] == er2[0] * er1[1]) {
    return er1[0] > er2[0];
  } else {
    return er1[0] * er2[1] > er2[0] * er1[1];
  }
}

vpii findHelperTree(int n, int m, vi &u, vi &v, vvi &g, vi &isRoyal) {
  DSU helperTreeDSU(n);
  vector<pii>helperTree;

  vector<array<int, 3>>edgeRatio(n);
  for (int i = 0; i < n; ++i) {
    edgeRatio[i] = {size(g[i]), size(g[i]), i};
  }
  sort(all(edgeRatio), cmp);
  for (int itr = 0; itr < n; ++itr) {
    int i = edgeRatio[0][2];
    DSU dsu(n);
    vi r;
    for (int j = 0; j < m; ++j) {
      if (u[j] != i && v[j] != i && dsu.Union(u[j], v[j])) {
        r.eb(j);
      }
    }
    vi roots;
    for (int j = 0; j < n; ++j) {
      if (j != i && dsu.par[j] < 0) {
        roots.eb(j);
      }
    }
    vvi group(n);
    for (int j : g[i]) {
      int other = u[j] + v[j] - i;
      group[dsu.Find(other)].eb(j);
    }
    for (int j = 0; j < dsu.components - 1; ++j) {
      for (int k = 0; k < dsu.components - 1; ++k) {
        if (k != j) {
          r.eb(group[roots[k]][0]);
        }
      }
      vi royals;
      int maxVal = -1;
      for (int k : group[roots[j]]) {
        if (isRoyal[k] == -1) {
          r.eb(k);
          royals.eb(count_common_roads(r));
          r.pop_back();
        } else if (isRoyal[k] == 1) {
          if (maxVal == -1) {
            r.eb(k);
            royals.eb(count_common_roads(r));
            r.pop_back();
            maxVal = royals.back();
          } else {
            royals.eb(maxVal);
          }
        } else {
          if (maxVal == -1) {
            r.eb(k);
            royals.eb(count_common_roads(r));
            r.pop_back();
            maxVal = royals.back() + 1;
          } else {
            royals.eb(maxVal - 1);
          }
        }
      }
      maxVal = (*max_element(all(royals)));
      for (int k = 0; k < size(group[roots[j]]); ++k) {
        int id = group[roots[j]][k];
        if (royals[k] == maxVal) {
          isRoyal[id] = 1;
        } else {
          isRoyal[id] = 0;
        }
        if (helperTreeDSU.Union(u[id], v[id])) {
          helperTree.eb(mpr(id, isRoyal[id]));
          if (helperTreeDSU.components == 1) return helperTree;
        }
      }
      for (int k = 0; k < dsu.components - 1; ++k) {
        if (k != j) {
          r.pop_back();
        }
      }
    }
    vector<set<int>>subTrees(n);
    for (int j = 0; j < m; ++j) {
      if (helperTreeDSU.Find(u[j]) != helperTreeDSU.Find(v[j])) {
        subTrees[u[j]].insert(helperTreeDSU.Find(v[j]));
        subTrees[v[j]].insert(helperTreeDSU.Find(u[j]));
      }
    }
    for (int j = 0; j < n; ++j) {
      edgeRatio[j] = {size(subTrees[j]), size(g[j]), j};
    }
    sort(all(edgeRatio), cmp);
  }
}

vi findDegrees(int n, int m, vpii &helperTree, vi &u, vi &v, vvi &g) {
  vi degree(n, 0);
  for (int i = 0; i < n; ++i) {
    DSU dsu(n);
    vi r;
    for (int j : g[i]) {
      dsu.Union(u[j], v[j]);
      r.eb(j);
    }
    for (auto [j, isRoyal] : helperTree) {
      if (dsu.Union(u[j], v[j])) {
        r.eb(j);
        degree[i] -= isRoyal;
      }
    }
    degree[i] += count_common_roads(r);
  }
  return degree;
}

int findRoyal(int n, vpii &helperTree, vi &edges, vi &u, vi &v) {
  int low = 0, high = size(edges) - 1;
  int mid;
  while (low < high) {
    mid = (low + high) >> 1;
    DSU dsu(n);
    vi r;
    int royals = 0;
    for (int i = low; i <= mid; ++i) {
      r.eb(edges[i]);
      dsu.Union(u[edges[i]], v[edges[i]]);
    }
    for (auto [i, isRoyal] : helperTree) {
      if (dsu.Union(u[i], v[i])) {
        r.eb(i);
        royals -= isRoyal;
      }
    }
    royals += count_common_roads(r);
    if (royals) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  return edges[low];
}
vi find_roads(int n, vi u, vi v) {
  int m = size(u);
  vvi g(n);
  for (int i = 0; i < m; ++i) {
    g[u[i]].eb(i);
    g[v[i]].eb(i);
  }
  vi isRoyal(m, -1);
  vpii helperTree = findHelperTree(n, m, u, v, g, isRoyal);
  vi degree = findDegrees(n, m, helperTree, u, v, g);


  queue<int>q;
  for (int i = 0; i < n; ++i) {
    if (degree[i] == 1) {
      q.push(i);
    }
  }
  vector<int>res;
  for (int i = 1; i < n; ++i) {
    int node = q.front();
    q.pop();
    vi edges;
    int id = -1;
    for (int i : g[node]) {
      if (isRoyal[i] == -1) {
        edges.eb(i);
      } else if (isRoyal[i] == 1) {
        id = i;
        break;
      }
    }
    if (id == -1) {
      id = findRoyal(n, helperTree, edges, u, v);
    }
    for (int i : edges) {
      isRoyal[i] = 0;
    }
    isRoyal[id] = 2;

    res.eb(id);

    int other = (u[id] ^ v[id] ^ node);
    --degree[other];
    if (degree[other] == 1) {
      q.push(other);
    }
  }
  return res;
}

컴파일 시 표준 에러 (stderr) 메시지

simurgh.cpp: In function 'std::vector<std::pair<int, int> > findHelperTree(int, int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<int>&)':
simurgh.cpp:67:22: warning: control reaches end of non-void function [-Wreturn-type]
   67 |   DSU helperTreeDSU(n);
      |                      ^

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30