oj.uz

Submission #107678

# Submission time Handle Problem Language Result Execution time Memory
107678 2019-04-25T12:29:49 Z MrTEK Parachute rings (IOI12_rings) C++14
0 / 100
 2272 ms 103964 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int dad[N][5],ans[5],deg[N][5],lst[5],wh[5],vis[N];
int n,m,cnt;
vector <int> ed[N];
pair <int,int> edge[N];
bool flag = 0;

int find(int u,int x) {
  if (dad[u][x] == u)
    return dad[u][x];
  return dad[u][x] = find(dad[u][x],x);
}

bool merge(int u,int v,int x) {
  int du = find(u,x);
  int dv = find(v,x);
  if (du == dv)
    return false;
  dad[du][x] = dv;
  return true;
}

void dfs(int cur) {
  if (vis[cur])
    return;
  cnt++;
  for (auto i : ed[cur])
    dfs(i);
}

int get(int cur) {
  cnt = 0;
  dfs(cur);
  return cnt;
}

void Init(int N_) {
  n = N_;
  for (int i = 0 ; i < 5 ; i++) {
    ans[i] = 1;
    lst[i] = 1;
    for (int j = 1 ; j <= n ; j++) {
      dad[j][i] = j;
      deg[j][i] = 0;
    }
  }
  ans[0] = n;
}

void Link(int A, int B) {
  A++ , B++;
  deg[A][0]++;
  deg[B][0]++;
  ed[A].push_back(B);
  ed[B].push_back(A);
  edge[++m] = {A,B};
  if (flag)
    return;
  if (deg[A][0] == 3) {
    int t = 1;
    wh[1] =  A;
    for (auto i : ed[A])
      wh[++t] = i;
    flag = true;
  }
  else if (deg[B][0] == 3) {
    int t = 1;
    wh[1] =  B;
    for (auto i : ed[B])
      wh[++t] = i;
    flag = true;
  }
  else if (merge(A,B,0) == false)
    ans[0] == n ? ans[0] = 0 : ans[0] = get(A);
}

int CountCritical() {
  if (flag == false)
    return ans[0];
  int res = 0;
  for  (int i = 1 ; i < 5 ; i++) {
    if (ans[i] == 0)
      continue;
    for ( ; lst[i] <= m ; lst[i]++) {
      int u = edge[lst[i]].first;
      int v = edge[lst[i]].second;
      if (u == wh[i] || v == wh[i])
        continue;
      deg[u][i]++;
      deg[v][i]++;
      if (deg[u][i] == 3 || deg[v][i] == 3 || merge(u,v,i) == false)
        ans[i] = 0;
    }
    res += ans[i];
  }
  return res;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 33 ms 24192 KB Output is correct
3 Correct 28 ms 24284 KB Output is correct
4 Incorrect 26 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 66184 KB Output is correct
2 Correct 2109 ms 88152 KB Output is correct
3 Correct 2272 ms 99292 KB Output is correct
4 Incorrect 1721 ms 103964 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 33 ms 24192 KB Output is correct
3 Correct 28 ms 24284 KB Output is correct
4 Incorrect 26 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 33 ms 24192 KB Output is correct
3 Correct 28 ms 24284 KB Output is correct
4 Incorrect 26 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23808 KB Output is correct
2 Correct 33 ms 24192 KB Output is correct
3 Correct 28 ms 24284 KB Output is correct
4 Incorrect 26 ms 23928 KB Output isn't correct
5 Halted 0 ms 0 KB -