제출 #796759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796759		vjudge1	Split the Attractions (IOI19_split)	C++17	22 / 100	178 ms	50100 KiB

split

#include "split.h"
#include "bits/stdc++.h"
using namespace std;
     
#define vi vector<int> 
#define ii pair<int,int>
#define all(x) x.begin(),x.end()

const int mxn=1e5+5;
vi adj[mxn],gra[mxn],res;
vector<ii> ed[mxn];
map<int,ii> temp_gra[mxn];
int timer,act,bad_col;
vi in,prof,id,tam;
vector<bool> is;
vector<vi> groups;

void dfs_cut(int u, int pa){
  in[u]=prof[u]=timer++;
  
  int aux=0;
  for(int v: adj[u]) if(v!=pa){
      if(in[v]==-1){
	dfs_cut(v,u);
	prof[u]=min(prof[u],prof[v]);
	
	if(prof[v]>=in[u] && pa!=-1) is[u]=true;
	
	aux++;
      }
      else prof[u]=min(prof[u],in[v]);
    }
  
  if(pa==-1 && aux>1) is[u]=true;
}
void find_cut(int n){
  timer=0;
  in.assign(n,-1); prof.assign(n,-1);
  is.assign(n,false);
  dfs_cut(0,-1);
}

void find_groups(int u, bool first){
  if(is[u]){id[u]=timer; return;}
  id[u]=timer;
  if(!first) groups[timer].push_back(u);
  for(int v: adj[u])
    if(id[v]==-1 && !is[v]) find_groups(v,false);
}
void make_size(int u, int pa){
  tam[u]=groups[u].size();
  for(int v: gra[u]) if(v!=pa){
      make_size(v,u);
      tam[u]+=tam[v];
    }
}
void make_groups(int n){
  id.assign(n,-1);
  timer=0;
  for(int i=0;i<n;i++)
    if(id[i]==-1){
      groups.push_back({i});
      find_groups(i,true);
      timer++;
    }

  for(int u=0;u<n;u++)
    if(is[u])
      for(int v: adj[u]){
	temp_gra[id[u]][id[v]]={u,v};
	temp_gra[id[v]][id[u]]={v,u};
      }
  for(int i=0;i<(int)groups.size();i++){
    for(auto x: temp_gra[i]){
      gra[i].push_back(x.first);
      ed[i].push_back(x.second);
    }
  } 
  
  tam.resize(n);
  make_size(0,-1);
}

void paint_group(int u, int act_id, int cant, int col){
  if(act>=cant) return;

  //printf("   paint %d\n",u);
  res[u]=col;
  act++;
  
  for(int v: adj[u])
    if(id[v]==act_id && res[v]==bad_col) paint_group(v,act_id,cant,col);
}
void paint(int u, int pa, int cant, int col){
  if(act>=cant) return;

  //printf("in group %d | using %d - %d con\n",u,temp_gra[pa][u].first,temp_gra[pa][u].second);
  //printf("group painted:\n");
  paint_group(temp_gra[u][pa].first,u,cant,col);
  //printf("\n");
  for(int v: gra[u])
    if(v!=pa) paint(v,u,cant,col);
}

vi find_split(int n, int a, int b, int c, vi p, vi q) {
  int m=(int)p.size();
  
  for(int i=0;i<m;i++)
    adj[p[i]].push_back(q[i]),adj[q[i]].push_back(p[i]);

  find_cut(n);
  make_groups(n);
  
  ii col[3]={{a,1},{b,2},{c,3}}; sort(col,col+3);
  bad_col=col[2].second;
  res.assign(n,bad_col);

  /*
  printf("left out %d\n\n",bad_col);
  for(int i=0;i<(int)groups.size();i++){
    printf("%d: ",i);
    for(int j: groups[i]) printf("%d ",j);
    printf("\n");
  }
  printf("\n");
  */
  
  vector<ii> con,edge;
  for(int i=0;i<(int)groups.size();i++)
    for(int j: gra[i])
      if(tam[i]>tam[j])
	con.push_back({i,j});
  
  bool found=false;
  for(int i=0;i<(int)con.size();i++){
    int u=con[i].first,v=con[i].second;

    int x=n-tam[v],y=tam[v];
    if(x>y) swap(u,v),swap(x,y);
    
    if(x<col[0].first || y<col[1].first) continue;

    //printf("%d: %d | %d: %d\n",u,x,v,y);
    
    act=0;
    //printf("paint from %d: %d %d\n",u,col[0].first,col[0].second);
    paint(u,v,col[0].first,col[0].second);
    //printf("\n");
    
    act=0;
    //printf("paint from %d: %d %d\n",v,col[1].first,col[1].second);
    paint(v,u,col[1].first,col[1].second);
    //printf("\n");
    
    found=true;
    break;
  }

  /*
  vi color[4];
  for(int i=0;i<n;i++) color[res[i]].push_back(i);
  for(int i=1;i<=3;i++){
    printf("%d: ",i);
    for(int j: color[i]) printf("%d ",j);
    printf(" -> %d\n",(int)color[i].size());
  }
  printf("\n");
  */
  
  return found ? res : vi (n,0);
}

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