oj.uz

Submission #1012757

# Submission time Handle Problem Language Result Execution time Memory
1012757 2024-07-02T14:42:50 Z Ludissey Parachute rings (IOI12_rings) C++14
0 / 100
 607 ms 98856 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
int n;
bool hasloop=false;
vector<vector<int>> neigh;
vector<int> critC;
vector<int> crit;
vector<int> low;
vector<int> tin;
vector<int> visited;
vector<int> critCOUNT;
int timer=0;
void detect_cycle(int x, int p) {
  visited[x]=true;
  low[x]=tin[x]=timer++;
  for (int to : neigh[x]) {
    if (to == p ) continue;
    if (visited[to]) {
      low[x] = min(low[x], tin[to]);
    } else {
        detect_cycle(to, x);
        low[x] = min(low[x], low[to]);
    }
  }
}

void Init(signed N_) {
  n = N_;
  neigh.resize(N_);
  critC.resize(N_);
  crit.resize(N_);
  critCOUNT.resize(N_);
  visited.resize(n,0);
  tin.resize(n,0);
  low.resize(n,0);
}

void Link(signed A, signed B) {
  neigh[A].push_back(B);
  neigh[B].push_back(A);
}

signed CountCritical() {
  int c=0;
  for (int i = 0; i < n; i++)
  {
    visited[i]=0;
    tin[i]=0;
    low[i]=0;
    critC[i]=0;
    crit[i]=0;
    critCOUNT[i]=0;
  }
  timer=0;
  for (int i = 0; i < n; i++) if(!visited[i]) detect_cycle(i,-1);
  vector<int> mp(n,0);
  int cyc=0;
  int cyl=-1;
  for (int i = 0; i < n; i++){
    mp[low[i]]++;
    if(mp[low[i]]==3) {
      cyc++;
      cyl=low[i];
    }
  }
  if(cyc>=2) return 0;
  for (int i = 0; i < n; i++) {
    if(cyc==0) critC[i]=true;
    else if(low[i]==cyl) critC[i]=true;
    else critC[i]=false;
  }
  int mx=0;
  for (int i = 0; i < n; i++) {
    if(sz(neigh[i])==3) {
      critCOUNT[i]++;
      critCOUNT[neigh[i][0]]++;
      critCOUNT[neigh[i][1]]++;
      critCOUNT[neigh[i][2]]++;
      mx++;
    }else if(sz(neigh[i])==4) {
      critCOUNT[i]++;
      mx++;
    }else if(sz(neigh[i])>4) return 0;
  }
  for (int i = 0; i < n; i++){
    if(critCOUNT[i]==mx&&critC[i]==true) crit[i]=true;
  }
  for (int i = 0; i < n; i++) { if(crit[i]) c++; }
  return c;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 2 ms 1044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 64340 KB Output is correct
2 Incorrect 607 ms 98856 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 2 ms 1044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 2 ms 1044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Incorrect 2 ms 1044 KB Output isn't correct
4 Halted 0 ms 0 KB -