제출 #143083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143083		model_code	Split the Attractions (IOI19_split)	C++17	40 / 100	220 ms	20728 KiB

split

// model_solution/split-kostka-greedy-dfs-tree.cpp
#include "bits/stdc++.h"
#include "split.h"

using namespace std;

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  srand(10);
  int m = (int)p.size();
  vector <pair <int, int> > sizes = {{a,1}, {b,2}, {c,3}};
  sort(sizes.begin(), sizes.end());
  a = sizes[0].first; b = sizes[1].first; c = sizes[2].first;
  vector <vector <int> > G(n);
  for(int i=0; i<m; i++) {
    G[p[i]].push_back(q[i]);
    G[q[i]].push_back(p[i]);
  }
  vector <vector <int> > T(n);
  vector <int> subtree(n), par(n);
  function <int(int)> dfs0 = [&](int v) {
    subtree[v] = 1;
    for(auto w : G[v]) if(!subtree[w]) {
      subtree[v] += dfs0(w);
      par[w] = v;
      T[v].push_back(w);
      T[w].push_back(v);
    }
    return subtree[v];
  };
  dfs0(0);
  for(int i=0; i<n; i++) {
    vector <bool> vis(n);
    vector <int> C;
    function <void(int, int, int)> dfs = [&](int v, int limit, int forbidden) {
      if((int)C.size() == limit) return;
      if(forbidden == v) return;
      C.push_back(v);
      vis[v] = true;
      for(auto w : T[v]) if(!vis[w]) dfs(w, limit, forbidden);
    };
    if(subtree[i] >= a and subtree[i] <= n-b) {
      vector <int> ret(n, sizes[2].second);
      dfs(i, a, par[i]);
      for(auto cc : C) ret[cc] = sizes[0].second;
      C.clear();
      dfs(par[i], b, i);
      for(auto cc : C) ret[cc] = sizes[1].second;
      return ret;
    } else if(subtree[i] >= b and subtree[i] <= n-a) {
      vector <int> ret(n, sizes[2].second);
      dfs(i, b, par[i]);
      for(auto cc : C) ret[cc] = sizes[1].second;
      C.clear();
      dfs(par[i], a, i);
      for(auto cc : C) ret[cc] = sizes[0].second;
      return ret;
    }
  }
  return vector<int>(n, 0);
}

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