oj.uz

답안 #1108114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1108114 2024-11-02T20:23:24 Z Lincito_31 낙하산 고리들 (IOI12_rings) C++17
37 / 100
 958 ms 74312 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,inde_t4=0,inde_t3=0;
vector<vector<int>> gra;
set<int> ciclos;
set<int> t3,t4;
ll res=-1;
vector<int> dsu;
vector<bool> visited;
bool cambio=false,xd=false;
int find(int a){
  if(dsu[a]==a){
    return a;
  }
  return dsu[a]=find(dsu[a]);
}
bool unir(int a, int b){
  a=find(a);b=find(b);
  if(a==b){
    return false;
  }
  if(ciclos.find(a)==ciclos.end()){
    dsu[a]=b;
  }else{
    dsu[b]=a;
  }
  return true;
}

void Init(int N_) {
  N=N_;
  dsu.resize(N);
  for(int i=0;i<N;i++){
    dsu[i]=i;
  }
  gra.resize(N);
  res=N;
}
void Link(int A, int B) {
  if(!unir(A,B)){
    ciclos.insert(find(A));
    cambio=true;
  }
  gra[A].push_back(B);
  if(gra[A].size()>=3){
    t3.insert(A);
    inde_t3=A;
    cambio=true;
  }
  if(gra[A].size()>=4){
    inde_t4=A;
    t4.insert(A);
    cambio=true;
  }
  gra[B].push_back(A);
  if(gra[B].size()>=3){
    t3.insert(B);
    inde_t3=B;
    cambio=true;
  }
  if(gra[B].size()>=4){
    inde_t4=B;
    t4.insert(B);
    cambio=true;
  }
}
void dfs(int now,int nooo,int ante){
  int conta=0;
  if(xd){
    return;
  }
  if(visited[now]){
    xd=true;
    return;
  }
  visited[now]=true;
  for(auto u:gra[now]){
    if(u==nooo || u==ante){
      continue;
    }
    dfs(u,nooo,now);
    conta++;
    if(conta>1){
      xd=true;
    }
    if(xd){
      return;
    }
  }
}
int CountCritical(){
  if(!cambio || res==0){
    // no paso nada
  }else if(t4.size()>=2){
    res=0;
  }else if(t3.size()>=5){
    res=0;
  }else if(ciclos.size()>=2){
    res=0;
  }else if(t4.size()==1){
    // si quito inde_t4 es un chain?
    xd=false;
    res=1;
    visited.assign(N,false);
    for(int i=0;i<N;i++){
      if(visited[i] || i==inde_t4){
        continue;
      }
      if(gra[i].size()==1){
        dfs(i,inde_t4,-1);
      }else if(gra[i].size()==2){
        if(gra[i][0]==inde_t4 || gra[i][1]==inde_t4){
          dfs(i,inde_t4,-1);
        }
      }
      if(xd){
        res=0;
        break;
      }
    }
    if(!xd){
      for(int i=0;i<N;i++){
        if(visited[i] || i==inde_t4 || dsu[i]==i){
          continue;
        }else{
          xd=true;
          res--;
          break;
        }
      }
    }
  }else if(t3.size()>=1){
    // si quito el inde_3 o sus vecinos sera un chain?
    xd=false;
    visited.assign(N,false);
    res=4;
    for(int i=0;i<N;i++){
      if(visited[i] || i==inde_t3){
        continue;
      }
      if(gra[i].size()==1){
        dfs(i,inde_t3,-1);
      }else if(gra[i].size()==2){
        if(gra[i][0]==inde_t3 || gra[i][1]==inde_t3){
          dfs(i,inde_t3,-1);
        }
      }
      if(xd){
        res--;
        break;
      }
    }
    if(!xd){
      for(int i=0;i<N;i++){
        if(visited[i] || i==inde_t3 || dsu[i]==i){
          continue;
        }else{
          xd=true;
          res--;
          break;
        }
      }
    }
    for(auto uu:gra[inde_t3]){
      xd=false;
      visited.assign(N,false);
      for(int i=0;i<N;i++){
        if(visited[i] || i==uu){
          continue;
        }
        if(gra[i].size()==1){
          dfs(i,uu,-1);
        }else if(gra[i].size()==2){
          if(gra[i][0]==uu || gra[i][1]==uu){
            dfs(i,uu,-1);
          }
        }
        if(xd){
          res--;
          break;
        }
      }
      if(!xd){
        for(int i=0;i<N;i++){
          if(visited[i] || i==uu || dsu[i]==i){
            continue;
          }else{
            xd=true;
            res--;
            break;
          }
        }
      }
    }
  }else if(ciclos.size()==1){
    //cuantos elementos pertenecen a este ciclo?
    int com=*ciclos.begin(),cont=0;
    for(int i=0;i<N;i++){
      if(find(i)==com){
        cont++;
      }
    }
    res=cont;
  }
  cambio=false;
  return res;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 2 ms 592 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 30772 KB Output is correct
2 Correct 470 ms 47692 KB Output is correct
3 Correct 843 ms 74312 KB Output is correct
4 Correct 508 ms 58952 KB Output is correct
5 Correct 518 ms 58952 KB Output is correct
6 Correct 568 ms 57792 KB Output is correct
7 Correct 828 ms 72264 KB Output is correct
8 Correct 958 ms 56076 KB Output is correct
9 Correct 725 ms 59976 KB Output is correct
10 Correct 367 ms 57672 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 6 ms 1104 KB Output is correct
13 Incorrect 7 ms 1104 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 3 ms 592 KB Output is correct
12 Correct 6 ms 1104 KB Output is correct
13 Incorrect 7 ms 1104 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 3 ms 848 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 171 ms 30772 KB Output is correct
12 Correct 470 ms 47692 KB Output is correct
13 Correct 843 ms 74312 KB Output is correct
14 Correct 508 ms 58952 KB Output is correct
15 Correct 518 ms 58952 KB Output is correct
16 Correct 568 ms 57792 KB Output is correct
17 Correct 828 ms 72264 KB Output is correct
18 Correct 958 ms 56076 KB Output is correct
19 Correct 725 ms 59976 KB Output is correct
20 Correct 367 ms 57672 KB Output is correct
21 Correct 3 ms 592 KB Output is correct
22 Correct 6 ms 1104 KB Output is correct
23 Incorrect 7 ms 1104 KB Output isn't correct
24 Halted 0 ms 0 KB -