oj.uz

Submission #350226

# Submission time Handle Problem Language Result Execution time Memory
350226 2021-01-19T04:27:55 Z casperwang Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 78760 KB 
#include <bits/stdc++.h>
#define pb push_back
#define All(x) x.begin(), x.end()
using namespace std;
#define debug(args) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

int N;
vector <int> dsu; // DSU
vector <int> sze; // SIZE of DSU
vector <int> deg; // degree
vector < vector<int> > path;
vector <int> nowCritical; // now answer

void Init(int n) {
  N = n;
  nowCritical.clear();
  dsu.clear(), dsu.resize(N);
  sze.clear(), sze.resize(N);
  deg.clear(), deg.resize(N);
  path.clear(), path.resize(N);
  for (int i = 0; i < N; i++) {
    dsu[i] = i;
    nowCritical.pb(i);
  }
}

int fnd(int a) {
  return dsu[a] == a ? dsu[a] : dsu[a] = fnd(dsu[a]);
}

void Union(int a, int b) {
  a = fnd(a), b = fnd(b);
  if (sze[a] > sze[b]) {
    sze[a] += sze[b];
    dsu[b] = a;
  } else {
    sze[b] += sze[a];
    dsu[a] = b;
  }
}

void Only(int v) {
  bool flag = 0;
  for (int i : nowCritical)
    if (i == v) flag = 1;
  nowCritical.clear();
  if (flag) nowCritical.pb(v);
  return;
}

void Left(int v) {
  vector <int> tmp;
  for (int i = 0; i < 3; i++)
    for (int j : nowCritical)
      if (j == path[v][i]) tmp.pb(j);
  for (int j : nowCritical)
    if (j == v) tmp.pb(v);
  nowCritical = tmp;
  return;
}

bool del(int id, int a, int b) {
  if (id == a || id == b) return 1;
  vector <int> vis(N);
  queue <int> nxt;
  nxt.push(a), vis[a] = 1;
  while (nxt.size() && !vis[b]) {
    int now = nxt.front();
    nxt.pop();
    for (int i : path[now]) {
      if (vis[i] || i == id) continue;
      vis[i] = 1, nxt.push(i);
    }
  }
  return !vis[b];
}

void BFS(int s, int t) {
  vector <int> cyc;
  for (int i = 0; i < N; i++) {
    if (fnd(i) == fnd(s) && del(i, s, t)) {
      cyc.pb(i);
    }
  }
  vector <int> tmp;
  for (int i : cyc)
    for (int j : nowCritical)
      if (i == j) tmp.pb(j);
  nowCritical = tmp;
  return;
}

void Link(int a, int b) {
  if (!nowCritical.size()) return;
  deg[a]++;
  if (deg[a] >= 4) Only(a);
  deg[b]++;
  if (deg[b] >= 4) Only(b);
  if (fnd(a) != fnd(b)) {
    Union(a, b);
  } else if (nowCritical.size()) {
    BFS(a, b);
  }
  path[a].pb(b);
  if (deg[a] == 3) Left(a);
  path[b].pb(a);
  if (deg[b] == 3) Left(b);
  return;
}

int CountCritical() {
  return nowCritical.size();
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 40 ms 620 KB Output is correct
6 Correct 194 ms 876 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 768 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 37092 KB Output is correct
2 Correct 926 ms 56796 KB Output is correct
3 Correct 291 ms 39908 KB Output is correct
4 Correct 1989 ms 78736 KB Output is correct
5 Execution timed out 4096 ms 78760 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 40 ms 620 KB Output is correct
6 Correct 194 ms 876 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 4 ms 748 KB Output is correct
12 Correct 14 ms 1132 KB Output is correct
13 Correct 6 ms 1132 KB Output is correct
14 Execution timed out 4090 ms 984 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 40 ms 620 KB Output is correct
6 Correct 194 ms 876 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 4 ms 748 KB Output is correct
12 Correct 14 ms 1132 KB Output is correct
13 Correct 6 ms 1132 KB Output is correct
14 Execution timed out 4090 ms 984 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 40 ms 620 KB Output is correct
6 Correct 194 ms 876 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 458 ms 37092 KB Output is correct
12 Correct 926 ms 56796 KB Output is correct
13 Correct 291 ms 39908 KB Output is correct
14 Correct 1989 ms 78736 KB Output is correct
15 Execution timed out 4096 ms 78760 KB Time limit exceeded
16 Halted 0 ms 0 KB -