oj.uz

Submission #350176

# Submission time Handle Problem Language Result Execution time Memory
350176 2021-01-19T03:57:44 Z casperwang Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 27696 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) {
  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;
}

void BFS(int s, int t) {
  queue <int> nxt;
  vector <bool> vis(N);
  vector <int> pre(N, -1);
  nxt.push(s), vis[s] = 1;
  while (!vis[t]) {
    int now = nxt.front();
    nxt.pop();
    srand(time(NULL));
    random_shuffle(All(path[now]));
    for (int i : path[now]) {
      if (vis[i]) continue;
      vis[i] = 1, pre[i] = now;
      nxt.push(i);
    }
  }
  vector <int> cyc;
  cyc.pb(t);
  while (pre[t] != -1) {
    cyc.pb(pre[t]);
    t = pre[t];
  }
  vector <int> tmp;
  for (int i : cyc)
    for (int j : nowCritical)
      if (i == j) tmp.pb(j);
  nowCritical = tmp;
}

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()) {
    for (int i = 0; i < 5; i++) {
      BFS(a, b);
    }
  }
  path[a].pb(b);
  if (deg[a] == 3) Left(a);
  path[b].pb(a);
  if (deg[b] == 3) Left(b);
  pary(All(nowCritical));
  return;
}

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 364 KB Output is correct
2 Execution timed out 4054 ms 5264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 364 KB Output is correct
2 Execution timed out 4054 ms 5264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 364 KB Output is correct
2 Execution timed out 4054 ms 5264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 364 KB Output is correct
2 Execution timed out 4054 ms 5264 KB Time limit exceeded
3 Halted 0 ms 0 KB -