Submission #143289

#	Time	Username	Problem	Language	Result	Execution time	Memory
143289		tpoppo	Split the Attractions (IOI19_split)	C++14	18 / 100	2072 ms	16248 KiB

split

#include "split.h"
#include<bits/stdc++.h>
#define lsb(x) (x&(-x))

using namespace std;
const int MAXN = 2e5 + 100;

using pii = pair<int,int>;
pii ord[3];
vector<int> res;

vector<int> grafo[MAXN];
vector<pii> edge;
int n;
mt19937 rng(3213123);

int parent[MAXN];
int find(int id){
  if(parent[id] == id) return id;
  return parent[id] = find(parent[id]);
}
bool merge(int a,int b){
  a = find(a);
  b = find(b);
  if(a == b) return false;
  parent[a] = b;
  return true;
}


void random_st(){
  for(int i=0;i<n;i++){
    grafo[i].clear();
    parent[i] = i;
  }
  shuffle(edge.begin(),edge.end(),rng);
  for(auto el : edge){
    //cout<<el.first<<" "<<el.second<<endl;
    if(merge(el.first,el.second)){
      grafo[el.first].emplace_back(el.second);
      grafo[el.second].emplace_back(el.first);
    }
  }
}

int block;
int req;
int rval;
int rid;
int dfs(int id,int prev){
  //cout<<prev<<" => "<<id<<endl;
  if(id == block) return 0;
  int sum = 1;
  for(auto el : grafo[id]){
    if(el != prev){
      sum += dfs(el,id);
    }
  }
  if(sum >= req && sum < rval){
    rval = sum;
    rid = id;
  }
  return sum;
}


int p1,p2;

void f(int id,int prev,int stato){
  if(id == p1) stato = 1;
  if(id == p2) stato = 2;
  switch(stato){
  case 1:
    if(ord[0].first){
      ord[0].first--;
      res[id] = ord[0].second;
    }
    break;
  case 2:
    if(ord[1].first){
      ord[1].first--;
      res[id] = ord[1].second;
    }
    break;
  }
  for(auto el : grafo[id]){
    if(el != prev){
      f(el,id,stato);
    }
  }
}




vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {


  res.resize(n);
  ::n = n;
  ord[0] = {a, 1};
  ord[1] = {b, 2};
  ord[2] = {c, 3};
  sort(ord,ord + 3);
  edge.reserve(p.size());
  for(int i=0;i<p.size();i++){
    edge.emplace_back(p[i],q[i]);
  }
  for(int _=0;_<100;_++){

    random_st();
    int root = rng()%n;
    rval = rid = 1e9;
    block = -1;
    req = ord[0].first;
    dfs(root,-1);
    //cout<<rid<<" - "<<rval<<endl;
    if(rval == 1e9) continue;
    p1 = rid;
    rval = rid = 1e9;
    block = p1;
    req = ord[1].first;
    dfs(root,-1);
    //cout<<rid<<" - "<<rval<<endl;
    p2 = rid;
    //cout<<root<<" "<<p1<<" "<<p2<<endl;
    if(p2 != 1e9){

      f(root,-1,0);
      for(auto&el:res){
        if(!el) el = ord[2].second;
      }
      return res;
    }
  }
	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<p.size();i++){
               ~^~~~~~~~~

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