oj.uz

Submission #917714

# Submission time Handle Problem Language Result Execution time Memory
917714 2024-01-28T16:37:12 Z anton Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 86236 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>

int N;
vector<vector<int>> adj;
vector<bool> passed;
vector<bool> cur_in;
set<pii> m;
vector<int> oc;



void Init(signed N_) {
  N = N_;
  oc.resize(5);
  adj.resize(N);
  cur_in.resize(N);
  passed.resize(N, false);
  set<int> l;
  for(int i= 0; i<N; i++){
    m.insert({0, i});
    oc[0]++;
  }
}
int flored(int id){
  return min(4LL, id);
}

void Link(signed A, signed B) {
  m.erase({adj[A].size(), A});
  m.erase({adj[B].size(), B});
  oc[flored(adj[A].size())]--;
  oc[flored(adj[B].size())]--;


  adj[A].push_back(B);
  adj[B].push_back(A);

  oc[flored(adj[A].size())]++;
  oc[flored(adj[B].size())]++;

  m.insert({adj[A].size(), A});
  m.insert({adj[B].size(), B});
}

int forbiden = 0;

bool dfs(int id, int anc){
  passed[id] = true;
  bool ok = true;
  for(auto v: adj[id]){
    if(v!=forbiden && v!=anc){
      if(passed[v]){
        return false;
      }
      else{
        ok &= dfs(v, id);
      }
    }
  }
  return ok;
}
bool test_crititcal(int id){
  forbiden = id;
  for(int i = 0; i<N; i++){  
    int deg =0;
    if(i == id){
      continue;
    }
    for(auto e: adj[i]){
      if(e!=id){
        deg++;
      }
    }
    if(deg>2){
      ////cout<<"deg "<<endl;
      return false;
    }
  }
  fill(passed.begin(), passed.end(), false);
  for(int i=  0; i<N; i++){
    if(!passed[i] && i!=forbiden){
      if(!dfs(i, -1)){
        ////cout<<"cycle "<<endl;
        return false;
      }
    }
  }
  return true;
}
int nbc = 0;

void nb_cycles(int u, int prev){
  passed[u] = true;
  for(auto v: adj[u]){
    if(v==prev){
      continue;
    }
    if(passed[v]){
      nbc++;
      //cout<<u<<" "<<v<<endl;
    }
    else{
      nb_cycles(v, u);
    }
  }
}
int find_intersection(int u, set<int>& res, int prev){
  passed[u] = true;
  cur_in[u] = true;
  int cur = 0;
  int ending = 0;
  bool founder = false;
  for(auto v: adj[u]){
    if(v==prev){
      continue;
    }
    if(passed[v]){
      //cout<<u<<" "<<v<<endl;
      if(cur_in[v]){
        cur++;
      }
      else{
        ending--;
      }
    }
    else{
      int child =find_intersection(v, res, u);
      if(child!=nbc){
        founder =true;
      }
      cur +=child; 
    }
  }
  if(cur == nbc && (ending !=0 || founder)){
    res.insert(u);
  }
  cur+=ending;
  cur_in[u] =false;
  return cur;
}
pair<bool, int> find_single(int u, int a, set<int>& s){
  passed[u] = true;
  for(auto v: adj[u]){
    if(v!=a){
      if(passed[v]){
        s.insert(u);
        return {true, v};
      }
      else{
        auto res = find_single(v, u, s);
        if(res.second == u){
          s.insert(u);
          return {false, -1};
        }
        else{
          if(res.first){
            s.insert(u);
            return res;
          }
        }
      }
    }
  }
  return {false, -1};
}
void find_ok_first(set<int>& ok){
  fill(passed.begin(), passed.end(), 0);
  nbc= 0;
  for(int i = 0; i<N; i++){
    if(!passed[i]){
      nb_cycles(i,-1);
    }
  }
  nbc/=2;
  //cout<<"nbc "<<nbc<<endl;
  if(nbc==0){
    for(int i = 0; i<N; i++){
      ok.insert(i);
    }
  }
  if(nbc==1){
    fill(passed.begin(), passed.end(), 0);
    for(int i = 0; i<N; i++){
      if(!passed[i]){
        find_single(i,-1, ok);
      }
    }
  }
  else{
  fill(passed.begin(), passed.end(), 0);
    for(int i = 0; i<N; i++){
      if(!passed[i]){
        find_intersection(i, ok, -1);
      }
    }
  }

  
  /*cout<<"ok "<<endl;
  for(auto e: ok){
    cout<<e<<" ";
  }
  cout<<endl;*/
}
signed CountCritical() {
  int res= 0;
  if(oc[4]>1){
    return 0;
  }
  else if(oc[4] == 1){
    int cand = m.lower_bound({4, 0})->second;
    if(test_crititcal(cand)){
      res++;
    }
    return res;
  }
  else{
    set<int> ok;

    for(int i = 0; i<N; i++){
      ok.insert(i);
    }
    
    if(oc[3]>0){
      auto it = m.lower_bound({3, 0});
      for(; it!=m.end(); ++it){
        set<int> neigs;
        for(auto e: adj[it->second]){
          neigs.insert(e);
        }
        neigs.insert(it->second);
        vector<int> rem;
        for(auto e: neigs){
          if(ok.find(e) == ok.end()){
            rem.push_back(e);
          }
        }
        for(auto e: rem){
          neigs.erase(e);
        }
        swap(ok, neigs);
      }
    }
    set<int> pass;
    for(auto e: ok){
      if(test_crititcal(e)){
        pass.insert(e);
      }
    }
    swap(pass, ok);
    return ok.size();
  }

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 121 ms 1072 KB Output is correct
6 Correct 468 ms 2040 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 79 ms 1116 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4017 ms 86236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 121 ms 1072 KB Output is correct
6 Correct 468 ms 2040 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 79 ms 1116 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Execution timed out 4058 ms 1628 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 121 ms 1072 KB Output is correct
6 Correct 468 ms 2040 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 79 ms 1116 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Execution timed out 4058 ms 1628 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 8 ms 604 KB Output is correct
5 Correct 121 ms 1072 KB Output is correct
6 Correct 468 ms 2040 KB Output is correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 79 ms 1116 KB Output is correct
9 Correct 6 ms 1368 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Execution timed out 4017 ms 86236 KB Time limit exceeded
12 Halted 0 ms 0 KB -