oj.uz

Submission #130622

# Submission time Handle Problem Language Result Execution time Memory
130622 2019-07-15T18:35:25 Z dragonslayerit Parachute rings (IOI12_rings) C++14
0 / 100
 4000 ms 262144 KB 
#include <vector>
#include <algorithm>
#include <cassert>

std::vector<std::pair<int,int> > elist;

int N;

struct Graph{
  int ign;
  std::vector<int> deg;
  std::vector<int> uf;
  bool fail;
  //std::vector<std::vector<int> > adj;
  Graph(int ign):ign(ign),deg(N),uf(N),fail(false)/*,adj(N)*/{
    for(int i=0;i<N;i++){
      uf[i]=i;
    }
  }
  int find(int a){
    while(a!=uf[a]){
      a=uf[a]=uf[uf[a]];
    }
    return a;
  }
  void merge(int a,int b){
    //adj[a].push_back(b);
    //adj[b].push_back(a);
    uf[find(a)]=find(b);
  }
  void add(int a,int b){
    if(a==ign||b==ign) return;
    if(++deg[a]>2) fail=true;
    if(++deg[b]>2) fail=true;
    if(find(a)==find(b)) fail=true;
    if(fail) return;
    merge(a,b);
  }
  /*
  std::vector<int> stk;
  std::vector<int> vis;
  bool dfs(int node,int parent){
    stk.push_back(node);
    vis[node]=1;
    for(int child:adj[node]){
      if(child==parent) continue;
      if(vis[child]){
	stk.erase(stk.begin(),std::find(stk.begin(),stk.end(),child));
	return true;
      }
      if(dfs(child,node)) return true;
    }
    stk.pop_back();
    return false;
  }
  std::vector<int> find_cycle(){
    vis.clear();
    vis.resize(N);
    for(int i=0;i<N;i++){
      if(!vis[i]&&dfs(i,i)){
	return stk;
      }
    }
    assert(0);
  }
  */
}all(-1);

std::vector<int> cycle;
std::vector<int> branch;

std::vector<struct Graph> checkers;

void Init(int N_) {
  N = N_;
  //all=Graph(-1);
  for(int i=0;i<N;i++){
    checkers.emplace_back(i);
  }
}

void AddBranch(int A){
  branch.push_back(A);
  checkers.emplace_back(A);
  for(auto e:elist){
    checkers.back().add(e.first,e.second);
  }
}

void Link(int A, int B) {
  /*
  if(branch.size()>2) return;
  if(++all.deg[A]==3){
    AddBranch(A);
  }
  if(++all.deg[B]==3){
    AddBranch(B);
  }
  if(all.find(A)==all.find(B)){
    if(cycle.empty()){
      cycle=all.find_cycle();
    }else{
      all.fail=true;
    }
  }
  all.merge(A,B);
  */
  for(auto& c:checkers){
    c.add(A,B);
  }
}

int CountCritical() {
  /*
  if(branch.empty()){
    if(all.fail) return 0;
    if(cycle.empty()) return N;
    return cycle.size();
  }
  if(branch.size()>2) return 0;
  */
  int ans=0;
  for(const auto& c:checkers){
    if(!c.fail) ans++;
  }
  return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 1613 ms 137968 KB Output is correct
3 Correct 2126 ms 196692 KB Output is correct
4 Correct 54 ms 8312 KB Output is correct
5 Correct 1259 ms 71284 KB Output is correct
6 Execution timed out 4045 ms 196592 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 1613 ms 137968 KB Output is correct
3 Correct 2126 ms 196692 KB Output is correct
4 Correct 54 ms 8312 KB Output is correct
5 Correct 1259 ms 71284 KB Output is correct
6 Execution timed out 4045 ms 196592 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 1613 ms 137968 KB Output is correct
3 Correct 2126 ms 196692 KB Output is correct
4 Correct 54 ms 8312 KB Output is correct
5 Correct 1259 ms 71284 KB Output is correct
6 Execution timed out 4045 ms 196592 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 1613 ms 137968 KB Output is correct
3 Correct 2126 ms 196692 KB Output is correct
4 Correct 54 ms 8312 KB Output is correct
5 Correct 1259 ms 71284 KB Output is correct
6 Execution timed out 4045 ms 196592 KB Time limit exceeded
7 Halted 0 ms 0 KB -