제출 #645142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645142		dattranxxx	Split the Attractions (IOI19_split)	C++17	18 / 100	116 ms	26580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
vector<int> adj[N];
int n, m;
vector<int> result;
int R = -1, R2 = 0, t = 0; pair<int, int> x[3];
int low[N], in[N], siz[N];
vector<int> tri[N];
void build(int u, int p = -1) {
  in[u] = low[u] = ++t;
  int flag = 1; siz[u] = 1;
  for (int v : adj[u]) if (v != p)
    if (in[v]) low[u] = min(low[u], in[v]);
    else tri[u].emplace_back(v), build(v, u), 
         low[u] = min(low[u], low[v]), siz[u] += siz[v], flag &= siz[v] < x[0].first;
  flag &= siz[u] >= x[0].first;
  if (flag) R = u;
}
int res[N], ans[N];
void dfs(int u, int c) {
  ans[u] = c;
  for (int v : tri[u])  
    dfs(v, c);
}
int fixx(int u) {
  res[u] = x[0].second; x[0].first--;
  if (x[0].first == 0) return 1;
  for (int v : tri[u]) if (ans[v] == x[0].second) {
    if (fixx(v)) return 1;
  }
  return 0;
}
void fixy(int u) {
  queue<int> q;
  q.emplace(u); vector<int> vis(n);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    vis[u] = 1, x[1].first--; res[u] = x[1].second;
    if (x[1].first == 0) break;
    for (int v : adj[u]) if (!vis[v] && ans[v] == x[2].second)
      vis[v] = 1, q.emplace(v);
  }
}
vector<int> print() {
  for (int v = 0; v < n; ++v) res[v] = x[2].second;
  fixx(R); fixy(R2);
  for (int v = 0; v < n; ++v)
    result.emplace_back(res[v]);
  return result;
}
vector<int> impossible() {
  result.clear();
  for (int v = 0; v < n; ++v)
    result.emplace_back(0);
  return result;
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
  n = _n, m = p.size();
  x[0] = {a, 1}, x[1] = {b, 2}, x[2] = {c, 3};
  sort(x, x + 3);
  for (int i = 0, u, v; i < m; ++i)
    u = p[i], v = q[i],
    adj[u].emplace_back(v),
    adj[v].emplace_back(u);
  build(0);
  if (R == -1) return impossible();
  dfs(0, x[2].second);
  dfs(R, x[0].second);
  int P1 = siz[R], P2 = n - P1;
  if (P2 < x[0].first) {
    for (int v : tri[R]) if (low[v] < in[R]) {
      dfs(v, x[2].second); P1 -= siz[v], P2 += siz[v];
      if (P2 >= x[0].first) break;
    }
  }
  vector<int> result = print();
  if (x[0].first || x[1].first) 
    return impossible();
  return result;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'void build(int, int)':
split.cpp:15:27: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   15 |   for (int v : adj[u]) if (v != p)
      |                           ^

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