oj.uz

Submission #350289

# Submission time Handle Problem Language Result Execution time Memory
350289 2021-01-19T04:47:27 Z casperwang Parachute rings (IOI12_rings) C++14
37 / 100
 1168 ms 73444 KB 
#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#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]);
}
 
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;
}
 
inline 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;
}
 
inline bool del(int id, int a, int b) {
  if (id == a || id == b) return 1;
  vector <bool> 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];
}
 
inline void check(int s, int t) {
  vector <int> tmp;
  for (int i : nowCritical)
    if (fnd(i) == fnd(s) && true)// || (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] > 3) Only(a);
  deg[b]++;
  if (deg[b] > 3) Only(b);
  if (fnd(a) != fnd(b)) {
    Union(a, b);
  } else if (nowCritical.size()) {
    check(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();
}

Compilation message

rings.cpp:2: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      |

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 2 ms 620 KB Output is correct
6 Correct 3 ms 748 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 3 ms 748 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 37016 KB Output is correct
2 Correct 878 ms 56944 KB Output is correct
3 Correct 273 ms 39908 KB Output is correct
4 Correct 1129 ms 70748 KB Output is correct
5 Correct 1168 ms 70916 KB Output is correct
6 Correct 1110 ms 73444 KB Output is correct
7 Correct 270 ms 40160 KB Output is correct
8 Correct 1062 ms 66268 KB Output is correct
9 Correct 1151 ms 70884 KB Output is correct
10 Correct 783 ms 69468 KB Output is correct

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 2 ms 620 KB Output is correct
6 Correct 3 ms 748 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 3 ms 748 KB Output is correct
11 Incorrect 3 ms 748 KB Output isn't correct
12 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 2 ms 620 KB Output is correct
6 Correct 3 ms 748 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 3 ms 748 KB Output is correct
11 Incorrect 3 ms 748 KB Output isn't correct
12 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 2 ms 620 KB Output is correct
6 Correct 3 ms 748 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 3 ms 748 KB Output is correct
11 Correct 457 ms 37016 KB Output is correct
12 Correct 878 ms 56944 KB Output is correct
13 Correct 273 ms 39908 KB Output is correct
14 Correct 1129 ms 70748 KB Output is correct
15 Correct 1168 ms 70916 KB Output is correct
16 Correct 1110 ms 73444 KB Output is correct
17 Correct 270 ms 40160 KB Output is correct
18 Correct 1062 ms 66268 KB Output is correct
19 Correct 1151 ms 70884 KB Output is correct
20 Correct 783 ms 69468 KB Output is correct
21 Incorrect 3 ms 748 KB Output isn't correct
22 Halted 0 ms 0 KB -