oj.uz

Submission #427702

# Submission time Handle Problem Language Result Execution time Memory
427702 2021-06-14T19:20:50 Z MarcoMeijer Parachute rings (IOI12_rings) C++14
0 / 100
 2713 ms 188536 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), e.end()

const int MX = 1e6+10;

int n;

struct DSU {
  int p[MX], r[MX], sz[MX], e[MX][2];
  int cnt[MX];
  int bigCnt = 0, smallCnt = 0;
  int cycles = 0, cycleLength = 0;
  void build() {
    RE(i,n) p[i] = i, r[i]=0, e[i][0]=e[i][1]=i, sz[i] = 1;
    RE(i,n) cnt[i] = 0;
  }
  int getSet(int x) {return x==p[x] ? x : p[x]=getSet(p[x]);}
  void link(int x, int y) {
    cnt[x]++;
    cnt[y]++;
    if(cnt[x] == 4) bigCnt++;
    if(cnt[y] == 4) bigCnt++;
    if(cnt[x] == 3) smallCnt++;
    if(cnt[y] == 3) smallCnt++;
    int u = getSet(x), v = getSet(y);
    if((e[u][0] == x && e[u][1] == y) || (e[u][0] == y && e[u][1] == x)) {
      cycles++;
      cycleLength = sz[u];
      return;
    }
    if(u != v) {
      sz[u] = sz[v] = sz[u] + sz[v];
      int i = 0, j = 0;
      if(e[u][0] != y) i = 1;
      if(e[v][0] != x) j = 1;
      e[u][i] = e[v][!j];
      RE(i,2) e[v][i] = e[u][i];
      if(r[u] > r[v]) {
        p[v] = u;
      } else {
        p[u] = v;
        if(r[u] == r[v]) r[v]++;
      }
    }
  }
};

DSU g;
vi adj[MX];
vii opperations;
bool started = false;
DSU other[4]; int ign[4];

void Init(int N_) {
  n = N_;
  g.build();
}

void createGraph(int i) {
  other[i].build();
  FOR(p,opperations) {
    int A = p.fi, B = p.se;
    if(A == ign[i] || B == ign[i])
      continue;
    other[i].link(A,B);
  }
}
void Link(int A, int B) {
  adj[A].pb(B);
  adj[B].pb(A);
  opperations.pb({A,B});
  g.link(A,B);
  if(started) {
    RE(i,4) {
      if(A == ign[i] || B == ign[i])
        continue;
      other[i].link(A,B);
    }
  }
  else if(adj[A].size() == 3 || adj[B].size() == 3) {
    int u = A;
    if(adj[B].size() == 3) u = B;
    ign[0] = u; int i=0;
    FOR(v,adj[u]) ign[++i] = v;
    RE(i,4) createGraph(i);
    started = true;
  }
}

int CountCritical() {
  if(g.bigCnt >= 2)
    return 0;
  if(started) {
    int cnt = 0;
    RE(i,4)
      if(other[i].cycles == 0 && other[i].smallCnt == 0)
        cnt++;
    return cnt;
  }
  if(g.cycles == 0)
    return n;
  if(g.cycles >= 2)
    return 0;
  return g.cycleLength;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 24612 KB Output is correct
3 Correct 17 ms 24888 KB Output is correct
4 Incorrect 14 ms 23848 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 56428 KB Output is correct
2 Correct 2320 ms 149544 KB Output is correct
3 Correct 2713 ms 188536 KB Output is correct
4 Incorrect 1649 ms 99756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 24612 KB Output is correct
3 Correct 17 ms 24888 KB Output is correct
4 Incorrect 14 ms 23848 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 24612 KB Output is correct
3 Correct 17 ms 24888 KB Output is correct
4 Incorrect 14 ms 23848 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 24612 KB Output is correct
3 Correct 17 ms 24888 KB Output is correct
4 Incorrect 14 ms 23848 KB Output isn't correct
5 Halted 0 ms 0 KB -