제출 #550957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550957		600Mihnea	Split the Attractions (IOI19_split)	C++17	40 / 100	1945 ms	24644 KiB

split

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

using namespace std;

mt19937 rng((long long)(new char));
///mt19937 rng(7777);

vector<int> solve(int n,vector<int> p, vector<int> q,int d1,int d2,double MAX_TIME){
  time_t bg=clock();
  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]);
  }
  bool done=0;
  int need=0;
  function<void(int, int,int)>place_to_all=[&](int a,int p,int value){
    if(need==0) return;
    assert(need>0);
    sol[a]=value;
    need--;
    for(auto&b:g[a]){
      if(b!=p&&sol[b]==0){
        place_to_all(b,a,value);
      }
    }
  };
  function<void(int, int)>dfs=[&](int a,int p){
    assert(0<=a&&a<n);
   /// cout<<"a = "<<a<<" "<<p<<"\n";
    if(done) return;
    sub[a]=1;
    for(auto&b:g[a]){
      if(b!=p){
        dfs(b,a);
        if(done) return;
        sub[a]+=sub[b];
      }
    }
    if(done) return;
    if(sub[a]>=d1&&n-sub[a]>=d2){
      done=1;
      need=d1;
      place_to_all(a,p,1);
      assert(need==0);
      need=d2;
      assert(p!=-1);
      place_to_all(p,-1,2);
      assert(need==0);
      return;
    }
    if(sub[a]>=d2&&n-sub[a]>=d1){
      done=1;
      need=d2;
      place_to_all(a,p,2);
      assert(need==0);
      need=d1;
      assert(p!=-1);

      place_to_all(p,-1,1);
      assert(need==0);
      return;
    }
  };

  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<bool> vis(n);
  vector<int> pr(n);

  function<void(int)>repg=[&](int a){
    assert(vis[a]==0);
    vis[a]=1;

    vector<int> kd;
    for(auto&b:g[a]){
      if(vis[b]==0){
        repg(b);
        pr[b]=a;
        kd.push_back(b);
      }
    }
    g[a]=kd;
  };

  while((double)(clock()-bg)/CLOCKS_PER_SEC<MAX_TIME){ /// redo so to calculate the time fewer times
    int root=rng()%n;

    if(0){
      shuffle(edges.begin(),edges.end(),rng);
      for(int i=0;i<n;i++) g[i].clear(),t[i]=i;

      int uni=0;

      for(auto&it:edges){

        if(get_root(it.first)!=get_root(it.second)){
          uni++;
          t[get_root(it.first)]=get_root(it.second);
          g[it.first].push_back(it.second);
          g[it.second].push_back(it.first);
        }
      }
      assert(uni==n-1);
    }else{
      for (int i=0;i<n;i++) g[i].clear(),vis[i]=0;
      for (auto&it:edges){
        g[it.first].push_back(it.second);
        g[it.second].push_back(it.first);
      }
      repg(root);
      for(int i=0;i<n;i++)assert(vis[i]);
      for(int i=0;i<n;i++){
        if(i!=root){
          g[i].push_back(pr[i]);
        }
      }
    }

    dfs(root,-1);

    if(done){
      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=i+1;j<3;j++){
      bool is_ok=0;
      is_ok|=((i==mn1&&j==mn2));
      is_ok|=((j==mn1&&i==mn2));
      if(!is_ok) continue;
      auto sol=solve(n,p,q,dims[i],dims[j],TIME_EACH);
      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);
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> solve(int, std::vector<int>, std::vector<int>, int, int, double)':
split.cpp:22:8: warning: unused variable 'ok' [-Wunused-variable]
   22 |   bool ok=1;
      |        ^~

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