Submission #1149687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149687		Sofiatpc	Parachute rings (IOI12_rings)	C++20	37 / 100	752 ms	103916 KiB

rings

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 1e6+5;
vector<int> adj[MAXN];
int v[MAXN], p[MAXN], dist[MAXN], n, qtd;

void Init(int N_) {
  n = N_;
}

void Link(int a, int b) {
  adj[a].push_back(b);
  adj[b].push_back(a);
}

void dfs(int s){
  for(int viz : adj[s]){
    if(dist[viz]){
      if(dist[viz] < dist[s] && viz != p[s]){
        if(p[viz] != -1)v[p[viz]]--;
        v[s]++;
        qtd++;
      }
      continue;
    }
    p[viz] = s;
    dist[viz] = dist[s]+1;
    dfs(viz);
    v[s] += v[viz];
  }

}

int CountCritical() {
  qtd = 0;
  for(int i = 0; i < n; i++){
    dist[i] = 0;
    v[i] = 0;
    p[i] = -1;
  }

  for(int i = 0; i < n; i++)
    if(!dist[i]){
      dist[i] = 1;
      dfs(i);
    }

  for(int i = 0; i < n; i++){
    if(sz(adj[i]) >= 4){
      qtd++; v[i]++;
    }else if(sz(adj[i]) == 3){
      qtd++; v[i]++;
      for(int viz : adj[i])v[viz]++;
    }
  }

  int ans = 0;
  for(int i = 0; i < n; i++)
    if(v[i] == qtd)ans++;

  return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31