Submission #468288

#	Time	Username	Problem	Language	Result	Execution time	Memory
468288		ivan_tudor	낙하산 고리들 (IOI12_rings)	C++14	100 / 100	1871 ms	191644 KiB

rings

#include<bits/stdc++.h>
using namespace std;
const int NMAX =  1000005;
vector<int> gr[NMAX];
struct chainsdsu{
  int dad;
  int l, r;
  int sz;
  bool iscycle;
};
int other(int x, int a1, int a2){ /// cel care nu e egal cu x, daca ambele sunt egale x
  if(x == a1)
    return a2;
  return a1;
}
struct chainDS{ /// pentru variantele care accepta doar lanturi => cand answer devine mic (leg lant de lant de necapete, leg un ciclu in interior, leg lant de ciclu)
  ///variante cand nu merge deloc : mai mult de un ciclu

  vector<chainsdsu> d;
  int N;
  bool ans;
  chainDS(int sz) : d(sz + 1), N(sz){
    for(int i = 1; i<= N; i++){
      d[i] = {i, i, i, 1, false};
    }
    ans = true;
  }
  int findd(int x){
    if(d[x].dad == x)
      return x;
    return d[x].dad = findd(d[x].dad);
  }
  bool AddEdge(int x, int y){
    int dx = findd(x);
    int dy = findd(y);
    if(dx == dy){
      ans = false;
      return ans;
    }
    if(!((x == d[dx].l || x == d[dx].r) && (y == d[dy].l || y == d[dy].r))){
      ans = false;
      return ans;
    }
    if(d[dx].sz < d[dy].sz){
      swap(dx, dy);
      swap(x, y);
    }
    d[dy].dad = dx;
    d[dx].l = other(x, d[dx].l, d[dx].r);
    d[dx].r = other(y, d[dy].l, d[dy].r);
    d[dx].sz += d[dy].sz;
    return ans;
  }
};
vector<pair<int, chainDS>> pos; /// nodurile ramase posibile
vector<pair<int, int>> edges;
chainsdsu d[NMAX];
int findd(int x){
  if(x == d[x].dad)
    return x;
  return d[x].dad = findd(d[x].dad);
}
int N;
int nrcycle = 0;
int cans = 0;
void Init(int N_) {
  N = N_;
  for(int i = 1; i<= N; i++){
    d[i] = {i, i, i, 1, false};
    gr[i].clear();
  }
  pos.clear();
  edges.clear();
  nrcycle = 0;
  cans = N;
}
void makepos(int A, int B){
  unordered_set<int> vec;
  for(auto x: gr[A])
    vec.insert(x);
  for(auto x: gr[B])
    vec.insert(x);
  for(auto x: vec){
    pos.push_back({x, chainDS(N)});
    for(auto e:edges){
      if(e.first != x && e.second != x){
        pos.back().second.AddEdge(e.first, e.second);
      }
    }
  }
}

void Link(int A, int B) {
  A++;
  B++;
  if(pos.size()){
    for(auto &x:pos){
      if(x.first != A && x.first != B)
        x.second.AddEdge(A, B);

    }
    return;
  }
  gr[A].push_back(B);
  gr[B].push_back(A);
  edges.push_back({A, B});
  chainsdsu &dA = d[findd(A)];
  chainsdsu &dB = d[findd(B)];

  if(dA.dad != dB.dad){
    /// cazul in care leg doua lanturi (bine sau gresit) sau un ciclu cu un lant

    if(dA.iscycle == false && dB.iscycle == false && (A == dA.l || A == dA.r) && (B == dB.l || B == dB.r)){
      /// cazul ok
      if(dA.sz > dB.sz){
        dB.dad = dA.dad;
        dA.sz += dB.sz;
        dA.l = other(A, dA.l, dA.r);
        dA.r = other(B, dB.l, dB.r);
      }
      else{
        dA.dad = dB.dad;
        dB.sz += dA.sz;
        dB.r = other(B, dB.l, dB.r);
        dB.l = other(A, dA.l, dA.r);

      }
      return;
    }
    /// stric ceva deci trebuie sa repar
    makepos(A, B);

  }
  else{
    /// cazul in care creez un ciclu
    if(dA.iscycle == false && ((A == dA.l && B == dA.r) || (A == dA.r && B == dA.l))){
      /// ciclu simplu
      dA.iscycle = true;
      nrcycle++;
      cans = dA.sz;
      return;
    }
    /// stric ceva deci trb sa fortez poz optime
    makepos(A, B);
  }
}

int CountCritical() {
  if(pos.size()){
    int ans = 0;
    for(auto &x:pos){
      if(x.second.ans == true)
        ans++;
    }
    return ans;
  }
  if(nrcycle > 1)
    return 0;
  return cans;

}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31