제출 #796666

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

split

#include "split.h"
#include "bits/stdc++.h"
using namespace std;
     
#define vi vector<int> 
#define ii pair<int,int>

const int mxn=1e5+5;
vi adj[mxn];
vi tam,res;
int act;

void init(int u, int pa){
  tam[u]=1;
  for(int v: adj[u]) if(v!=pa){
      init(v,u);
      tam[u]+=tam[v];
    }
}

void paint(int u, int pa, int cant, int col){
  if(act>=cant) return;
  res[u]=col,act++;
  for(int v: adj[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();

  if(m!=n-1) return vi (n,0);
  
  for(int i=0;i<m;i++)
    adj[p[i]].push_back(q[i]),adj[q[i]].push_back(p[i]);

  tam.resize(n);
  init(0,-1);

  ii col[3]={{a,1},
	     {b,2},
	     {c,3}};
  sort(col,col+3);
  res.assign(n,col[2].second);
  
  bool found=false;
  for(int i=0;i<m;i++){
    int u=p[i],v=q[i];
    if(tam[u]<tam[v]) swap(u,v);

    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;
    
    act=0;
    paint(u,v,col[0].first,col[0].second);
    act=0;
    paint(v,u,col[1].first,col[1].second);
    found=true;
    break;
  }
  
  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