oj.uz

Submission #350212

# Submission time Handle Problem Language Result Execution time Memory
350212 2021-01-19T04:18:11 Z casperwang Parachute rings (IOI12_rings) C++14
0 / 100
 1046 ms 70692 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.clear();
  nowCritical = tmp;
  return;
}

void BFS(int s, int t, bool flag) {
  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();
    if (flag) {
      for (int _i = 0; _i < path[now].size(); _i++) {
        int i = path[now][_i];
        if (vis[i]) continue;
        vis[i] = 1, pre[i] = now;
        nxt.push(i);
      }
    } else {
      for (int _i = path[now].size()-1; _i >= 0; _i--) {
        int i = path[now][_i];
        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.clear();
  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()) {
    BFS(a, b, 1);
    BFS(a, b, 0);
  }
  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: In function 'void BFS(int, int, bool)':
rings.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       for (int _i = 0; _i < path[now].size(); _i++) {
      |                        ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
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 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 37092 KB Output is correct
2 Correct 835 ms 56724 KB Output is correct
3 Correct 297 ms 39908 KB Output is correct
4 Incorrect 1046 ms 70692 KB Output isn't correct
5 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 Incorrect 1 ms 364 KB Output isn't correct
5 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 Incorrect 1 ms 364 KB Output isn't correct
5 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 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -