Submission #287764

#	Time	Username	Problem	Language	Result	Execution time	Memory
287764		Haunted_Cpp	Split the Attractions (IOI19_split)	C++17	7 / 100	98 ms	15064 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 5;

bool vis[MAX_N];

vector<vector<int>> g(MAX_N);

vector<int> euler;
vector<int> ans;

void dfs(int node) {
  vis[node] = true;
  euler.emplace_back(node);
  for (auto to : g[node]) {
    if (!vis[to]) {
      vis[to] = true;
      dfs(to);
    }
  }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  vector<int> in(n);
  ans = vector<int>(n, -1);
  const int m = p.size();
  assert(m <= n);
  memset(vis, false, sizeof(vis));
  for (int i = 0; i < m; i++) {
    int st = p[i];
    int et = q[i];
    g[st].emplace_back(et);
    g[et].emplace_back(st);
  }
  dfs(0);
  vector<int> res(n);
  for (auto to : euler) {
    if (a) {
      res[to] = 1;
      --a;
    } else if (b) {
      res[to] = 2;
      --b;
    } else {
      res[to] = 3;
    }
  }
	return res;
}

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