oj.uz

Submission #350231

# Submission time Handle Problem Language Result Execution time Memory
350231 2021-01-19T04:29:51 Z casperwang Parachute rings (IOI12_rings) C++14
20 / 100
 4000 ms 75180 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.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:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |       for (int _i = 0; _i < path[now].size(); _i++) {
      |                        ~~~^~~~~~~~~~~~~~~~~~

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 36964 KB Output is correct
2 Correct 902 ms 56672 KB Output is correct
3 Correct 292 ms 39908 KB Output is correct
4 Correct 1385 ms 74952 KB Output is correct
5 Execution timed out 4075 ms 75180 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 6 ms 620 KB Output is correct
6 Correct 18 ms 748 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 4 ms 748 KB Output is correct
11 Incorrect 4 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 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 6 ms 620 KB Output is correct
6 Correct 18 ms 748 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 4 ms 748 KB Output is correct
11 Incorrect 4 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 748 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 6 ms 620 KB Output is correct
6 Correct 18 ms 748 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 4 ms 748 KB Output is correct
11 Correct 462 ms 36964 KB Output is correct
12 Correct 902 ms 56672 KB Output is correct
13 Correct 292 ms 39908 KB Output is correct
14 Correct 1385 ms 74952 KB Output is correct
15 Execution timed out 4075 ms 75180 KB Time limit exceeded
16 Halted 0 ms 0 KB -