Submission #645128

#	Time	Username	Problem	Language	Result	Execution time	Memory
645128		dattranxxx	Split the Attractions (IOI19_split)	C++17	Compilation error	0 ms	0 KiB

split

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
vector<pair<int, int>> adj[N];
int n, m;
void impossible() {
  for (int v = 0; v < n; ++v)
    cout << 0 << ' ';
  exit(0);
}
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 e = -1) {
  in[u] = low[u] = ++t;
  int flag = 1; siz[u] = 1;
  for (auto& c : adj[u]) if (c.second != e) {
    int v = c.first;
    if (in[v]) low[u] = min(low[u], low[v]);
    else tri[u].emplace_back(v), build(v, c.second), 
         low[u] = min(low[u], in[v]), siz[u] += siz[v], flag &= siz[v] < x[0].first;
  }
  flag &= siz[u] >= x[0].first;
  if (flag && R == -1) 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;
}
int fixy(int u) {
  res[u] = x[1].second; x[1].first--;
  if (x[1].first == 0) return 1;
  for (int v : tri[u]) if (ans[v] == x[2].second) {
    if (fixy(v)) return 1;
  }
  return 0;
}
vector<int> print() {
  for (int v = 0; v < n; ++v) res[v] = x[2].second;
  fixx(R); fixy(R2); 
  vector<int> result(n);
  for (int i = 0; i < n; ++i)
    result[i] = res[i];
  return result;
}
int P1, P2;
void dfs2(int u) {
  for (int v : tri[u]) if (low[v] < in[R]) {
    if (P1 - siz[v] >= x[0].first)
      P1 -= siz[v], P2 += siz[v], dfs(v, x[2].second);
    else dfs2(v);
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  cin >> n >> m;
  for (int i = 0; i < 3; ++i) cin >> x[i].first, x[i].second = i + 1;
  sort(x, x + 3);
  for (int i = 0, u, v; i < m; ++i)
    cin >> u >> v,
    adj[u].emplace_back(v, i),
    adj[v].emplace_back(u, i);
  build(0);
  if (R == -1) impossible();
  for (int v = 0; v < n; ++v) ans[v] = x[2].second;
  dfs(R, x[0].second);
  P1 = siz[R], P2 = n - P1;
  dfs2(R);
  vector<int> result = print();
  if (x[0].first || x[1].first) 
    impossible();
  for (int x : result) cout << x << ' ';
	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc6w5ym7.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cchSKFs8.o:split.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc6w5ym7.o: in function `main':
grader.cpp:(.text.startup+0x266): undefined reference to `find_split(int, int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status