Submission #439416

#	Time	Username	Problem	Language	Result	Execution time	Memory
439416		prvocislo	Parachute rings (IOI12_rings)	C++17	0 / 100	4065 ms	70924 KiB

rings

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n;
vector<int> g[maxn];
vector<pair<int, int> > e;
struct dsu
{
  int p[maxn], deg[maxn], ok, r;
  int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
  void merge(int a, int b)
  {
    if (r == a || r == b || !ok) return;
    if (deg[a] == 2 || deg[b] == 2 || find(a) == find(b)) return ok = 0, void();
    deg[a]++, deg[b]++;
    p[find(a)] = find(b);
  }
  dsu(int root)
  {
    ok = 1, r = root;
    for (int i = 0; i < n; i++) p[i] = i, deg[i] = 0;
    for (pair<int, int> i : e) merge(i.first, i.second);
  }
};
int p[maxn], s[maxn], cycle = 0;
bool bad = false;
vector<dsu> sp;
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
bool merge(int a, int b)
{
  a = find(a), b = find(b);
  if (a == b) return false;
  p[b] = a, s[a] += s[b];
  return true;
}
void Init(int N_) {
  n = N_;
  for (int i = 0; i < n; i++) p[i] = i, s[i] = 1;
}
void Link(int a, int b) {
  if (bad) return;
  if (sp.size()) 
  {
    for (dsu &i : sp) i.merge(a, b);
    return;
  }
  g[a].push_back(b), g[b].push_back(a); e.push_back({a, b});
  if (g[a].size() < g[b].size()) swap(a, b);
  if (g[a].size() == 3)
  {
    sp.push_back(dsu(a));
    for (int i : g[a]) sp.push_back(dsu(i));
    return; 
  }
  if (!merge(a, b))
  {
    if (cycle) return bad = true, void();
    cycle = s[a];
  }
}
int CountCritical() {
  if (bad) return 0;
  if (sp.size())
  {
    int ans = 0;
    for (dsu &i : sp) ans += i.ok;
    return ans;
  }
  return cycle ? cycle : n;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31