Submission #515846

#	Time	Username	Problem	Language	Result	Execution time	Memory
515846		DanerZein	Split the Attractions (IOI19_split)	C++14	18 / 100	2013 ms	12636 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
vector<vi> G;
vector<ii> ab;
vector<int> res;
int n,m;
int tam;
bool colorear(int u,int col){
  res[u]=col;
  tam--;
  if(tam==0) return 1;
  for(auto &v:G[u]){
    if(res[v]==0 && colorear(v,col))
      return 1;
  }
  return 0;
}
bool sepuede(int ro){
  for(int i=0;i<n;i++) res[i]=0;
  tam=ab[0].first;
  colorear(ro,ab[0].second);
  int col=4;
  bool se=0;
  for(int i=0;i<n;i++){
    if(res[i]==0){
      col++;
      tam=ab[1].first;
      if(colorear(i,col)){
	se=1;
	break;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(res[i]!=ab[0].second && res[i]!=col) res[i]=ab[2].second;;
    if(res[i]==col) res[i]=ab[1].second;
  }
  return se;
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
  n=nn;
  m=p.size();
  G.resize(n+1);
  res.resize(n);
  for(int i=0;i<m;i++){
    int a=p[i],b=q[i];
    G[a].push_back(b);
    G[b].push_back(a);
  }
  ab={ii(a,1),ii(b,2),ii(c,3)};
  sort(ab.begin(),ab.end());
  bool sw=0;
  for(int i=0;i<n;i++){
    if(sepuede(i)){
      sw=1;
      break;
    }
  }
  if(!sw) for(int i=0;i<n;i++) res[i]=0;
  return res;
}

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