Submission #1149710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149710		Sofiatpc	Parachute rings (IOI12_rings)	C++20	20 / 100	4096 ms	97940 KiB

rings

#include <bits/stdc++.h>

using namespace std;

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

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){
  vector<int> temp;
  for(int viz : adj[s])
    if(dist[viz] && dist[viz] < dist[s] && viz != p[s]){
      for(int j = sz(b)-1; j >= 0; j--){
        if(dist[b[j].fi] < dist[viz])break;
        if(dist[b[j].sc] < dist[viz]){
          v[s]++; v[viz]++;
          v[p[b[j].fi]]--;
          if(p[b[j].sc] != -1)v[p[b[j].sc]]--;
        }else{
          v[s]++; 
          if(p[viz] != -1)v[viz]--;
          v[p[b[j].fi]]--;
          v[b[j].sc]++;
        }
        qtd++;
      }

      v[s]++;
      if(p[viz] != -1)v[p[viz]]--;
      qtd++;
      temp.push_back(viz);
    }

  for(int i = 0; i < sz(temp); i++)b.emplace_back(s,temp[i]);

  for(int viz : adj[s])
    if(!dist[viz]){
      p[viz] = s;
      dist[viz] = dist[s]+1;
      dfs(viz);
      v[s] += v[viz];
    }
  
  for(int i = 0; i < sz(temp); i++)b.pop_back();
    
}

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: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31