oj.uz

Submission #917670

# Submission time Handle Problem Language Result Execution time Memory
917670 2024-01-28T14:41:38 Z anton Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 68396 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;


void Init(signed N_) {
  N = N_;
  adj.resize(N);
  passed.resize(N, false);
  set<int> l;
  for(int i= 0; i<N; i++){
    m.insert({0, i});
  }
}

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

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

  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;
}
signed CountCritical() {

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

}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 32 ms 860 KB Output is correct
3 Correct 13 ms 1116 KB Output is correct
4 Correct 7 ms 572 KB Output is correct
5 Correct 104 ms 912 KB Output is correct
6 Correct 476 ms 1328 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 71 ms 896 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 9 ms 996 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4021 ms 68396 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 344 KB Output is correct
2 Correct 32 ms 860 KB Output is correct
3 Correct 13 ms 1116 KB Output is correct
4 Correct 7 ms 572 KB Output is correct
5 Correct 104 ms 912 KB Output is correct
6 Correct 476 ms 1328 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 71 ms 896 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 9 ms 996 KB Output is correct
11 Execution timed out 4037 ms 968 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 344 KB Output is correct
2 Correct 32 ms 860 KB Output is correct
3 Correct 13 ms 1116 KB Output is correct
4 Correct 7 ms 572 KB Output is correct
5 Correct 104 ms 912 KB Output is correct
6 Correct 476 ms 1328 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 71 ms 896 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 9 ms 996 KB Output is correct
11 Execution timed out 4037 ms 968 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 344 KB Output is correct
2 Correct 32 ms 860 KB Output is correct
3 Correct 13 ms 1116 KB Output is correct
4 Correct 7 ms 572 KB Output is correct
5 Correct 104 ms 912 KB Output is correct
6 Correct 476 ms 1328 KB Output is correct
7 Correct 5 ms 860 KB Output is correct
8 Correct 71 ms 896 KB Output is correct
9 Correct 6 ms 1116 KB Output is correct
10 Correct 9 ms 996 KB Output is correct
11 Execution timed out 4021 ms 68396 KB Time limit exceeded
12 Halted 0 ms 0 KB -