Submission #550953

#	Time	Username	Problem	Language	Result	Execution time	Memory
550953		600Mihnea	Split the Attractions (IOI19_split)	C++17	40 / 100	1595 ms	28868 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]);
  };

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

    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=0.5;
  vector<int> dims={a, b, c};

  for (int i=0;i<3;i++){
    for(int j=i+1;j<3;j++){
      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);
}

Compilation message (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