oj.uz

Submission #917720

# Submission time Handle Problem Language Result Execution time Memory
917720 2024-01-28T16:44:03 Z anton Parachute rings (IOI12_rings) C++17
38 / 100
 4000 ms 92960 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);
  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, unordered_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, unordered_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(unordered_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==1){
    fill(passed.begin(), passed.end(), 0);
    for(int i = 0; i<N; i++){
      if(!passed[i]){
        find_single(i,-1, ok);
      }
    }
  }
  else if(oc[3]>0 || nbc == 0){
    for(int i = 0; i<N; i++){
      ok.insert(i);
    }
  }
  /*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{
    unordered_set<int> ok;

    find_ok_first(ok);

    if(oc[3]>0){
      auto it = m.lower_bound({3, 0});
      for(; it!=m.end(); ++it){
        unordered_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);
      }
      unordered_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 344 KB Output is correct
2 Correct 4 ms 1112 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 6 ms 1548 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 6 ms 1116 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 Correct 2372 ms 83448 KB Output is correct
2 Execution timed out 4035 ms 92960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 1112 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 6 ms 1548 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Correct 25 ms 1232 KB Output is correct
12 Correct 69 ms 1880 KB Output is correct
13 Correct 85 ms 2016 KB Output is correct
14 Correct 21 ms 1628 KB Output is correct
15 Correct 30 ms 2388 KB Output is correct
16 Correct 67 ms 1960 KB Output is correct
17 Correct 76 ms 1956 KB Output is correct
18 Correct 35 ms 2996 KB Output is correct
19 Correct 73 ms 1876 KB Output is correct
20 Correct 87 ms 1884 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 1112 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 6 ms 1548 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Correct 25 ms 1232 KB Output is correct
12 Correct 69 ms 1880 KB Output is correct
13 Correct 85 ms 2016 KB Output is correct
14 Correct 21 ms 1628 KB Output is correct
15 Correct 30 ms 2388 KB Output is correct
16 Correct 67 ms 1960 KB Output is correct
17 Correct 76 ms 1956 KB Output is correct
18 Correct 35 ms 2996 KB Output is correct
19 Correct 73 ms 1876 KB Output is correct
20 Correct 87 ms 1884 KB Output is correct
21 Execution timed out 4030 ms 7644 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 1112 KB Output is correct
3 Correct 5 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 6 ms 1548 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Correct 2372 ms 83448 KB Output is correct
12 Execution timed out 4035 ms 92960 KB Time limit exceeded
13 Halted 0 ms 0 KB -