Submission #880029

#	Time	Username	Problem	Language	Result	Execution time	Memory
880029		ximeji5589	Split the Attractions (IOI19_split)	C++14	Compilation error	0 ms	0 KiB

split

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int cnt, low[N], num[N], par[N], sz[N];
vector<int> adj[N], nadj[N];
pair<int, int> x[5];
int n, m, res[N];

template<class X, class Y>
void cmnum(X &x, const Y &y) {
  if (x > y) x = y;
}

void dfs(int p, int u) {
  par[u] = p;
  sz[u] = 1;
  low[u] = num[u] = ++cnt;
  for (auto c : adj[u]) {
    if (num[c])
      cmnum(low[u], num[c]);
    else {
      dfs(u, c);
      nadj[u].push_back(c);
      sz[u] += sz[c];
      cmnum(low[u], low[c]);
    }
  }
}

bool stop = false;

bool nwrip[N];

map<int, bool> rip;

int cnt_comp;

void dfs_co1(int u, int co) {
  if (cnt_comp < x[co].first) {
    res[u] = x[co].second;
    cnt_comp++;
    nwrip[u] = true;
  }
  for (auto c : nadj[u])
    if (!rip[c])
      dfs_co1(c, co);
}

bool vis[N];

void dfs_co2(int u, int co) {
  vis[u] = true;
  if (cnt_comp < x[co].first) {
    res[u] = x[co].second;
    cnt_comp++;
  }
  for (auto c : adj[u])
    if (res[c] == x[3].second && !vis[c])
      dfs_co2(c, co);
}

void dfs2(int u) {
  if (stop) return;
  bool wtf = true;
  for (auto c : nadj[u])
    wtf &= (sz[c] < x[1].first);
  if (wtf && sz[u] >= x[1].first) {
    rip.clear();
    int siu = n - sz[u];
    for (auto c : nadj[u]) {
      if (low[c] < num[u] && siu < x[1].first) {
        siu += sz[c];
        rip[c] = true;
      }
    }
    if (siu >= x[1].first) {
      for (int i = 1; i <= n; i++)
        res[i] = x[3].second;
      if (siu >= x[2].first) {
        dfs_co1(u, 1);
        cnt_comp = 0;
        dfs_co2(par[u], 2);
      } else {
        dfs_co1(u, 2);
        cnt_comp = 0;
        dfs_co2(par[u], 1);
      }
      stop = true;
    }
  }
  for (auto c: nadj[u]) dfs2(c);
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
  
  cin >> n >> m;
  
  for (int i = 1; i <= 3; i++)
    cin >> x[i].first, x[i].second = i;
  
  sort(x + 1, x + 4);

  for (int i = 1; i <= m; i++) {
    int u, v; cin >> u >> v; u++; v++;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  dfs(0, 1);
  dfs2(1);
  
  for (int i = 1; i <= n; i++)
    cout << res[i] << ' ';

	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccUqImlP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccJngJmQ.o:split.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUqImlP.o: in function `main':
grader.cpp:(.text.startup+0x25e): 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