oj.uz

Submission #917735

# Submission time Handle Problem Language Result Execution time Memory
917735 2024-01-28T16:59:28 Z anton Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 167020 KB 
#include<bits/stdc++.h>
#pragma("03")
using namespace std;

#define pii pair<int, int>

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



void Init(signed N_) {
  N = N_;
  oc.resize(5);
  adj.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(4, 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[B].size(), B});
}

int forbiden = 0;
bool acyclic = true;

void dfs(int id, int anc){
  passed[id] = true;
  for(auto v: adj[id]){
    if(v!=forbiden && v!=anc){
      if(passed[v]){
        acyclic = false;
      }
      else{
        dfs(v, id);
      }
    }
  }
}
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);
  acyclic = true;
  for(int i=  0; i<N; i++){
    if(!passed[i] && i!=forbiden){
      dfs(i, -1);
    }
  }
  return acyclic;
}
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);
    }
  }
}
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 calc_cycles(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;
}
void find_ok_first(set<int>& ok){
  
  
  /*cout<<"ok "<<endl;
  for(auto e: ok){
    cout<<e<<" ";
  }
  cout<<endl;*/
}
signed CountCritical() {

  m.clear();
  for(int i = 0; i<N; i++){
    m.insert({adj[i].size(), i});
  }
  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;

    calc_cycles(ok);
    if(nbc==1){
      fill(passed.begin(), passed.end(), 0);
      for(int i = 0; i<N; i++){
        if(!passed[i]){
          find_single(i,-1, ok);
        }
      }
    }
    if(oc[3]>0){
      auto it = m.lower_bound({3, 0});
      vector<int> off(N);
      for(; it!=m.end(); ++it){
        set<int> neigs;
        for(auto e: adj[it->second]){
          off[e]++;
        }
        off[it->second]++;
      }
      set<int> pass;
      for(int i = 0; i<N; i++){
        if(off[i] == oc[3]){
          if(test_crititcal(i)){
            pass.insert(i);
          }
        }
      }
      return pass.size();
    }
    else if(nbc==0){
      return N;
    }
    
    return ok.size();
  }

}

Compilation message

rings.cpp:2: warning: ignoring '#pragma ( ' [-Wunknown-pragmas]
    2 | #pragma("03")
      |

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 1 ms 660 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 4 ms 856 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 53396 KB Output is correct
2 Correct 1033 ms 83284 KB Output is correct
3 Correct 1040 ms 110936 KB Output is correct
4 Correct 1645 ms 116308 KB Output is correct
5 Correct 1640 ms 118124 KB Output is correct
6 Correct 1950 ms 167020 KB Output is correct
7 Correct 1070 ms 109836 KB Output is correct
8 Correct 1892 ms 112152 KB Output is correct
9 Correct 1727 ms 120256 KB Output is correct
10 Correct 1074 ms 116824 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 1 ms 660 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 33 ms 964 KB Output is correct
12 Correct 101 ms 1388 KB Output is correct
13 Correct 124 ms 1316 KB Output is correct
14 Correct 81 ms 1332 KB Output is correct
15 Correct 193 ms 2132 KB Output is correct
16 Correct 98 ms 1308 KB Output is correct
17 Correct 102 ms 1360 KB Output is correct
18 Correct 188 ms 2440 KB Output is correct
19 Correct 110 ms 1560 KB Output is correct
20 Correct 120 ms 1364 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 1 ms 660 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 33 ms 964 KB Output is correct
12 Correct 101 ms 1388 KB Output is correct
13 Correct 124 ms 1316 KB Output is correct
14 Correct 81 ms 1332 KB Output is correct
15 Correct 193 ms 2132 KB Output is correct
16 Correct 98 ms 1308 KB Output is correct
17 Correct 102 ms 1360 KB Output is correct
18 Correct 188 ms 2440 KB Output is correct
19 Correct 110 ms 1560 KB Output is correct
20 Correct 120 ms 1364 KB Output is correct
21 Execution timed out 4051 ms 4524 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 3 ms 1372 KB Output is correct
7 Correct 1 ms 660 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 474 ms 53396 KB Output is correct
12 Correct 1033 ms 83284 KB Output is correct
13 Correct 1040 ms 110936 KB Output is correct
14 Correct 1645 ms 116308 KB Output is correct
15 Correct 1640 ms 118124 KB Output is correct
16 Correct 1950 ms 167020 KB Output is correct
17 Correct 1070 ms 109836 KB Output is correct
18 Correct 1892 ms 112152 KB Output is correct
19 Correct 1727 ms 120256 KB Output is correct
20 Correct 1074 ms 116824 KB Output is correct
21 Correct 33 ms 964 KB Output is correct
22 Correct 101 ms 1388 KB Output is correct
23 Correct 124 ms 1316 KB Output is correct
24 Correct 81 ms 1332 KB Output is correct
25 Correct 193 ms 2132 KB Output is correct
26 Correct 98 ms 1308 KB Output is correct
27 Correct 102 ms 1360 KB Output is correct
28 Correct 188 ms 2440 KB Output is correct
29 Correct 110 ms 1560 KB Output is correct
30 Correct 120 ms 1364 KB Output is correct
31 Execution timed out 4051 ms 4524 KB Time limit exceeded
32 Halted 0 ms 0 KB -