oj.uz

답안 #350300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
350300 2021-01-19T04:51:04 Z casperwang 낙하산 고리들 (IOI12_rings) C++14
20 / 100
 4000 ms 77412 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))
      tmp.pb(i);
  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();
    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] > 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);
    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();
}

Compilation message

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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 13 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
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 458 ms 36944 KB Output is correct
2 Correct 904 ms 56796 KB Output is correct
3 Correct 282 ms 39908 KB Output is correct
4 Correct 1191 ms 74844 KB Output is correct
5 Correct 1386 ms 75036 KB Output is correct
6 Execution timed out 4106 ms 77412 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 13 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 13 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 896 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 13 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 458 ms 36944 KB Output is correct
12 Correct 904 ms 56796 KB Output is correct
13 Correct 282 ms 39908 KB Output is correct
14 Correct 1191 ms 74844 KB Output is correct
15 Correct 1386 ms 75036 KB Output is correct
16 Execution timed out 4106 ms 77412 KB Time limit exceeded
17 Halted 0 ms 0 KB -