oj.uz

Submission #439416

# Submission time Handle Problem Language Result Execution time Memory
439416 2021-06-29T19:20:16 Z prvocislo Parachute rings (IOI12_rings) C++17
0 / 100
 4000 ms 70924 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31564 KB Output is correct
2 Correct 144 ms 70924 KB Output is correct
3 Correct 162 ms 70836 KB Output is correct
4 Incorrect 41 ms 31564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4065 ms 42084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31564 KB Output is correct
2 Correct 144 ms 70924 KB Output is correct
3 Correct 162 ms 70836 KB Output is correct
4 Incorrect 41 ms 31564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31564 KB Output is correct
2 Correct 144 ms 70924 KB Output is correct
3 Correct 162 ms 70836 KB Output is correct
4 Incorrect 41 ms 31564 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 31564 KB Output is correct
2 Correct 144 ms 70924 KB Output is correct
3 Correct 162 ms 70836 KB Output is correct
4 Incorrect 41 ms 31564 KB Output isn't correct
5 Halted 0 ms 0 KB -