oj.uz

Submission #350265

# Submission time Handle Problem Language Result Execution time Memory
350265 2021-01-19T04:39:34 Z casperwang Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 78608 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, cnt;
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]);
}
 
inline 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;
  }
}
 
inline 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 j : nowCritical) {
    for (int i = 0; i < 3; i++)
      if (j == path[v][i]) tmp.pb(j);
    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> tmp;
  for (int i : nowCritical)
    if (fnd(i) == fnd(s) && del(i, s, t))
      tmp.pb(i);
  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()) {
    cnt++;
    assert(cnt < 20);
    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 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 36 ms 620 KB Output is correct
6 Correct 174 ms 832 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 36964 KB Output is correct
2 Correct 894 ms 56800 KB Output is correct
3 Correct 273 ms 39908 KB Output is correct
4 Correct 1481 ms 78608 KB Output is correct
5 Execution timed out 4101 ms 78608 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 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 36 ms 620 KB Output is correct
6 Correct 174 ms 832 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 6 ms 1264 KB Output is correct
13 Correct 5 ms 1132 KB Output is correct
14 Runtime error 3 ms 1644 KB Execution killed with signal 6 (could be triggered by violating memory limits)
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 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 36 ms 620 KB Output is correct
6 Correct 174 ms 832 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 6 ms 1264 KB Output is correct
13 Correct 5 ms 1132 KB Output is correct
14 Runtime error 3 ms 1644 KB Execution killed with signal 6 (could be triggered by violating memory limits)
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 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 36 ms 620 KB Output is correct
6 Correct 174 ms 832 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 469 ms 36964 KB Output is correct
12 Correct 894 ms 56800 KB Output is correct
13 Correct 273 ms 39908 KB Output is correct
14 Correct 1481 ms 78608 KB Output is correct
15 Execution timed out 4101 ms 78608 KB Time limit exceeded
16 Halted 0 ms 0 KB -