oj.uz

Submission #917698

# Submission time Handle Problem Language Result Execution time Memory
917698 2024-01-28T15:22:28 Z anton Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 108628 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;
set<pii> m;
vector<int> oc;

vector<int> ending;


void Init(signed N_) {
  N = N_;
  oc.resize(5);
  adj.resize(N);
  ending.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;
  int cur = 0;
  for(auto v: adj[u]){
    if(v==prev){
      continue;
    }
    if(passed[v]){
      ending[v] ++;
      cur++;
    }
    else{
      cur += find_intersection(v, res, u);
    }
  }
  cur-=ending[u];
  if(cur == nbc){
    res.insert(u);
  }
  return cur;
}
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;

    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;

    fill(passed.begin(), passed.end(), 0);
    fill(ending.begin(), ending.end(), 0);
    for(int i = 0; i<N; i++){
      if(!passed[i]){
        find_intersection(i, ok, -1);
      }
    }

    //cout<<"initial ok"<<endl;
    for(auto e: ok){
      //cout<<e<<" ";
    }
    //cout<<endl;
    
    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);
      }
    }
    return ok.size();
  }


 for(int i = 0; i<N; i++){
  if(test_crititcal(i)){
    ////cout<<i<<" ";
    res++;
  }
 }
 return res;

}

Compilation message

rings.cpp: In function 'int CountCritical()':
rings.cpp:166:14: warning: unused variable 'e' [-Wunused-variable]
  166 |     for(auto e: ok){
      |              ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 5 ms 1116 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 1372 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 7 ms 1372 KB Output is correct
10 Correct 8 ms 1624 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2655 ms 93816 KB Output is correct
2 Execution timed out 4046 ms 108628 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 5 ms 1116 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 1372 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 7 ms 1372 KB Output is correct
10 Correct 8 ms 1624 KB Output is correct
11 Incorrect 33 ms 1280 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 5 ms 860 KB Output is correct
3 Correct 5 ms 1116 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 1372 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 7 ms 1372 KB Output is correct
10 Correct 8 ms 1624 KB Output is correct
11 Incorrect 33 ms 1280 KB Output isn't correct
12 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 5 ms 860 KB Output is correct
3 Correct 5 ms 1116 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 1372 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 7 ms 1372 KB Output is correct
10 Correct 8 ms 1624 KB Output is correct
11 Correct 2655 ms 93816 KB Output is correct
12 Execution timed out 4046 ms 108628 KB Time limit exceeded
13 Halted 0 ms 0 KB -