Submission #551023

#	Time	Username	Problem	Language	Result	Execution time	Memory
551023		600Mihnea	Split the Attractions (IOI19_split)	C++17	100 / 100	287 ms	38508 KiB

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;


vector<int> solve(int n,vector<int> p, vector<int> q,int d1,int d2){
  assert(d1<=d2);
  assert((int)p.size()==(int)q.size());
  vector<pair<int, int>> edges((int)p.size());
  for(int i=0;i<(int)p.size();i++) {
    edges[i]={p[i], q[i]};
  }
  vector<int> sol(n,0);

  vector<vector<int>> g(n);

  vector<int> sub(n,0);

  bool ok=1;
  for(int i=0;i<(int)p.size();i++){
    g[p[i]].push_back(q[i]);
    g[q[i]].push_back(p[i]);
  }
  auto gi=g;
  bool done=0;
  int need=0;
  vector<int> is_blo(n);
  function<void(int, int)>place_to_all=[&](int a,int value){
    assert(is_blo[a]==0);
    if(need==0) return;
    assert(need>0);
    sol[a]=value;
    need--;
    for(auto&b:gi[a]){
      if(is_blo[b]==1) continue;
      if(sol[b]==0){
        place_to_all(b,value);
      }
    }
  };

  vector<int> t(n);

  function<int(int)>get_root=[&](int a){
    if(t[a]==a) return a;
    return t[a]=get_root(t[a]);
  };

  vector<vector<int>> back_edges(n);
  vector<bool> vis(n);
  vector<int> pr(n);
  vector<int> dep(n,0);
  vector<int> min_dep(n,0);

  int vertex=-1;
  vector<int> par_of(n);

  function<void(int)>buildg=[&](int a){
    min_dep[a]=dep[a];
    assert(vis[a]==0);
    vis[a]=1;
    sub[a]=1;

    vector<int> kd;
    for(auto&b:g[a]){
      if(vis[b]==0){
        par_of[b]=a;
        dep[b]=1+dep[a];
        buildg(b);
        sub[a]+=sub[b];
        pr[b]=a;
        kd.push_back(b);
        min_dep[a]=min(min_dep[a],min_dep[b]);
      }else{
        if(dep[b]<dep[a]-1){
          back_edges[a].push_back(b);
          min_dep[a]=min(min_dep[a],dep[b]);
        }
      }
    }
    g[a]=kd;
    if(sub[a]>=d1&&vertex==-1){
      vertex=a;
    }
  };

  for (auto&it:edges){
    g[it.first].push_back(it.second);
    g[it.second].push_back(it.first);
  }

  buildg(0);

  assert(vertex!=-1);

  int have=sub[vertex];

  vector<int> yes,no;

  for(auto &b:g[vertex]){
    if(min_dep[b]<dep[vertex]&&have-sub[b]>=d1){
      have-=sub[b];
      no.push_back(b);
    }else{
      yes.push_back(b);
    }
  }


  function<int()> getcnt=[&](){
    int sol=0;
    for(auto&x:is_blo)sol+=(x==0);
    return sol;
  };

  function<void(int)>toggle_blo=[&](int a){
    is_blo[a]^=1;
    for(auto&b:g[a]) toggle_blo(b);
  };

  assert(par_of[vertex]!=-1);
  assert((int)is_blo.size()==n);


  if(have>=d1&&n-have>=d2){
    need=d1;
    for (int i=0;i<n;i++) is_blo[i]=1;
    toggle_blo(vertex);
    for(auto&v:no) toggle_blo(v);
    place_to_all(vertex,1);
    assert(getcnt()==have);



    assert(need==0);


    need=d2;
    for(int i=0;i<n;i++) is_blo[i]=1;
    toggle_blo(0);
    toggle_blo(vertex);
    for(auto&v:no) toggle_blo(v);

    assert(getcnt()==n-have);

    place_to_all(par_of[vertex],2);
    assert(need==0);
    return sol;
  }

  if(have>=d2&&n-have>=d1){
    need=d2;
    for (int i=0;i<n;i++) is_blo[i]=1;
    toggle_blo(vertex);
    for(auto&v:no) toggle_blo(v);
    place_to_all(vertex,2);
    assert(need==0);


    need=d1;
    for(int i=0;i<n;i++) is_blo[i]=1;
    toggle_blo(0);
    toggle_blo(vertex);
    for(auto&v:no) toggle_blo(v);

    place_to_all(par_of[vertex],1);
    assert(need==0);
    return sol;
  }

  return {};
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res;
  double TIME_EACH=1.9;
  vector<int> dims={a, b, c};

  int mn1,mn2;

  {
    vector<int> aux=dims;
    mn1=min_element(aux.begin(),aux.end())-aux.begin();
    aux[mn1]=(int)1e9+7;

    mn2=min_element(aux.begin(),aux.end())-aux.begin();;
  }

  for (int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      bool is_ok=0;
      is_ok|=((i==mn1&&j==mn2));
      if(!is_ok) continue;
      auto sol=solve(n,p,q,dims[i],dims[j]);
      if(sol.empty()) continue;
      int c1=0,c2=0;
      for (auto &it:sol){
        assert(it==0||it==1||it==2);
        c1+=(it==1);
        c2+=(it==2);
      }
      assert(c1==dims[i]);
      assert(c2==dims[j]);
      for (auto &it:sol){
        if(it==0){
          it=3-i-j;
        }else{
          if(it==1){
            it=i;
          }else{
            assert(it==2);
            it=j;
          }
        }
        it++;
        assert(1<=it&&it<=3);
      }
      return sol;
    }
  }
	return vector<int>(n,0);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> solve(int, std::vector<int>, std::vector<int>, int, int)':
split.cpp:20:8: warning: unused variable 'ok' [-Wunused-variable]
   20 |   bool ok=1;
      |        ^~
split.cpp:26:8: warning: unused variable 'done' [-Wunused-variable]
   26 |   bool done=0;
      |        ^~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:177:10: warning: unused variable 'TIME_EACH' [-Wunused-variable]
  177 |   double TIME_EACH=1.9;
      |          ^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36