Submission #893496

#	Time	Username	Problem	Language	Result	Execution time	Memory
893496		KaleemRazaSyed	Split the Attractions (IOI19_split)	C++17	100 / 100	99 ms	31068 KiB

split

#include<bits/stdc++.h>

using namespace std;
#define vec vector<int>

const int N = 1e5+5;
vec G[N];
vec ans;
int colors[] = {1, 2, 3}, sz[N], n, h[N], minh[N], cnt[3];
bool seen[N], colored;

void dfs0(int v)
{
  if(cnt[0] == 0 || ans[v] != 0)
    return;
  //cerr << "dfs0 : " << v << ' ' << colors[0] << endl;
  cnt[0]--;
  ans[v] = colors[0];
  for(int u : G[v])
    if(cnt[0] > 0 && h[u] > h[v])
      dfs0(u);
}
void dfs1(int v)
{
  //cerr << "dfs1 : " << v << ' ' << colors[1] << endl;
  cnt[1]--;
  ans[v] = colors[1];
  for(int u : G[v])
    if(cnt[1] > 0 and ans[u] == 0)
      dfs1(u);
}

void dfs(int v, int p = N)
{
  seen[v] = true;
  sz[v] = 1;
  h[v] = h[p] + 1;
  minh[v] = h[v];
  bool t = false;
  vec children;
  for(int u : G[v])
    if(!seen[u])
      {
	children.push_back(u);
	dfs(u, v);
	t |= (sz[u] >= cnt[0]);
	sz[v] += sz[u];
	minh[v] = min(minh[u], minh[v]);
      }
    else
      minh[v] = min(minh[v], h[u]);
      

  if(!t && sz[v] >= cnt[0] && !colored){
    // forced size
    int fsize = 0;
    vec back;
    for(int c : children)
      if(minh[c] >= h[v])
	fsize += sz[c];
      else
	back.push_back(c);
    fsize++; // v itself
    while(fsize < cnt[0] && back.size())
      {
	fsize += sz[back.back()];
	back.pop_back();
      }

    if(fsize >= cnt[1] and n - fsize >= cnt[0])
      swap(cnt[1], cnt[0]), swap(colors[0], colors[1]);

    if(fsize >= cnt[0] and n - fsize >= cnt[1]){
      ans[v] = colors[0];
      cnt[0]--;
      colored = true;
      int p = 0;
      for(int u : children)
	{
	  if(p < back.size() and back[p] == u){
	    p++;
	    continue;
	  }
	  dfs0(u);
	}
      
    }
    
  }
  
}

vec find_split(int n, int a, int b, int c, vec p, vec q)
{
  ::n = n;
  for(int i = 0; i < q.size(); i++)
    {
      G[q[i]].push_back(p[i]);
      G[p[i]].push_back(q[i]);
    }

  if(a > b)
    swap(a, b), swap(colors[0], colors[1]);
  if(b > c)
    swap(b, c), swap(colors[1], colors[2]);
  if(a > b)
    swap(a, b), swap(colors[0], colors[1]);

  cnt[0] = a, cnt[1] = b, cnt[2] = c;
  for(int j = 0; j < 1; j++)
    {
      ans = vec(n, 0);
      dfs(j);
      
      if(colored)
	for(int i : ans)
	  if(i == 0)
	    {
	      dfs1(i);
	      break;
	    }
      if(colored)
	for(int &i : ans)
	  if(i == 0) i = colors[2];
      if(colored) break;
    }
  return ans;
}
/*
int main() {
  int n, m, a, b, c;
  assert(5 == scanf("%d %d %d %d %d", &n, &m, &a, &b, &c));
  vector<int> p(m), q(m);
  for (int i=0; i<m; i++)
    assert(2 == scanf("%d %d", &p[i], &q[i]));
  
  vector<int> result = find_split(n, a, b, c, p, q);
  
  for (int i=0; i<(int)result.size(); i++)
    printf("%d ", result[i]);
  printf("\n");
  return 0;
}
// */

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int)':
split.cpp:80:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    if(p < back.size() and back[p] == u){
      |       ~~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int i = 0; i < q.size(); i++)
      |                  ~~^~~~~~~~~~

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