oj.uz

Submission #1012772

# Submission time Handle Problem Language Result Execution time Memory
1012772 2024-07-02T15:04:05 Z Ludissey Parachute rings (IOI12_rings) C++14
0 / 100
 751 ms 151680 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;
int exceptation=-1;


void detect_cycle(int x, int p) {
  visited[x]=true;
  low[x]=tin[x]=timer++;
  for (int to : neigh[x]) {
    if (to == p ||to==exceptation) 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;
  int mx=0;
  int center=-1;
  exceptation=-1;
  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]++;
      center=i;
      mx++;
    }
  }
  for (int i = 0; i < n; i++){
    mp[low[i]]++;
    if(mp[low[i]]==3) {
      cyc++;
      cyl=low[i];
    }
  }
  if(cyc>=2) {
    exceptation=center;
    for (int i = 0; i < n; i++) if(!visited[i]) detect_cycle(i,-1);\
    cyc=0;
    for (int i = 0; i < n; i++){
      mp[low[i]]++;
      if(mp[low[i]]==3) {
        cyc++;
        cyl=low[i];
      }
    }
    if(cyc==0) return 1;
    else 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;
  }
  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 344 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 700 KB Output is correct
8 Incorrect 1 ms 860 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 64156 KB Output is correct
2 Correct 523 ms 98948 KB Output is correct
3 Correct 684 ms 139088 KB Output is correct
4 Correct 725 ms 123736 KB Output is correct
5 Correct 734 ms 124488 KB Output is correct
6 Correct 751 ms 151680 KB Output is correct
7 Correct 738 ms 135760 KB Output is correct
8 Correct 725 ms 115548 KB Output is correct
9 Correct 739 ms 124240 KB Output is correct
10 Incorrect 578 ms 125724 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 700 KB Output is correct
8 Incorrect 1 ms 860 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 700 KB Output is correct
8 Incorrect 1 ms 860 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 2 ms 1116 KB Output is correct
7 Correct 1 ms 700 KB Output is correct
8 Incorrect 1 ms 860 KB Output isn't correct
9 Halted 0 ms 0 KB -