oj.uz

Submission #144406

# Submission time Handle Problem Language Result Execution time Memory
144406 2019-08-16T20:15:11 Z xiaowuc1 Split the Attractions (IOI19_split) C++14
40 / 100
 129 ms 14016 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

vector<int> edges[100005];

int ufpar[100005];
int ufsz[100005];

int find(int x) {
  return ufpar[x] == x ? x : (ufpar[x] = find(ufpar[x]));
}
bool merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x == y) return false;
  if(ufsz[x] < ufsz[y]) swap(x, y);
  ufsz[x] += ufsz[y];
  ufpar[y] = x;
  return true;
}

// spanning tree is rooted at 0
int treeSize[100005];
int dfsParent[100005];
bool dfsSeen[100005];
int assignedColor[100005];
int ret[100005];

bool ufcolor(int curr, int need, int want) {
  ret[curr] = want;
  if(--need == 0) return true;
  queue<int> q;
  q.push(curr);
  while(!q.empty()) {
    curr = q.front(); q.pop();
    for(int out: edges[curr]) {
      if(find(out) != find(curr)) continue;
      if(ret[out]) continue;
      ret[out] = want;
      if(--need == 0) return true;
      q.push(out);
    }
  }
  return false;
}

vector<int> consolidate(int n) {
  vector<int> ans;
  for(int i = 0; i < n; i++) {
    assert(ret[i] >= 1 && ret[i] <= 3);
    ans.push_back(ret[i]);
  }
  return ans;
}

void downColor(int curr, int par, int& need, int want) {
  ret[curr] = want;
  assert(need > 0);
  if(--need == 0) return;
  for(int out: edges[curr]) {
    if(out == par || need == 0) continue;
    downColor(out, curr, need, want);
  }
}

bool upColor(int curr, int need, int want) {
  queue<int> q;
  q.push(curr);
  ret[curr] = want;
  if(--need == 0) return true;
  while(!q.empty()) {
    curr = q.front(); q.pop();
    for(int out: edges[curr]) {
      if(ret[out]) continue;
      ret[out] = want;
      if(--need == 0) return true;
      q.push(out);
    }
  }
  return false;
}

void fillRest(int n, int want) {
  for(int i = 0; i < n; i++) {
    if(ret[i] == 0) ret[i] = want;
  }
}

void dfs(int curr, int par) {
  treeSize[curr] = 1;
  dfsSeen[curr] = true;
  dfsParent[curr] = par;
  for(int out: edges[curr]) {
    if(dfsSeen[out]) continue;
    dfs(out, curr);
    treeSize[curr] += treeSize[out];
  }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  for(int i = 0; i < p.size(); i++) {
    edges[p[i]].push_back(q[i]);
    edges[q[i]].push_back(p[i]);
  }
  dfs(0, -1);
  vector<pii> sizes;
  sizes.emplace_back(a, 1);
  sizes.emplace_back(b, 2);
  sizes.emplace_back(c, 3);
  sort(sizes.begin(), sizes.end());
  // is there a subtree such that it can be colored with size a and the other half can be colored with size b
  for(int i = 1; i < n; i++) {
    if(treeSize[i] >= sizes[0].first && n-treeSize[i] >= sizes[1].first) {
      downColor(i, dfsParent[i], sizes[0].first, sizes[0].second);
      assert(upColor(dfsParent[i], sizes[1].first, sizes[1].second));
      fillRest(n, sizes[2].second);
      return consolidate(n);
    }
    if(treeSize[i] >= sizes[1].first && n-treeSize[i] >= sizes[0].first) {
      downColor(dfsParent[i], i, sizes[0].first, sizes[0].second);
      assert(upColor(i, sizes[1].first, sizes[1].second));
      fillRest(n, sizes[2].second);
      return consolidate(n);
    }
  }
  // find a node such that, when deleted, all trees have size < a
  int critical = -1;
  for(int i = 0; i < n; i++) {
    int largestTree = 0;
    int parentSize = n-1;
    for(int out: edges[i]) {
      if(dfsParent[out] != i) continue;
      largestTree = max(largestTree, treeSize[out]);
      parentSize -= treeSize[out];
    }
    largestTree = max(largestTree, parentSize);
    if(largestTree >= sizes[0].first) continue;
    critical = i;
    break;
  }
  assert(critical != -1);
  for(int i = 0; i < n; i++) {
    ufpar[i] = i;
    ufsz[i] = 1;
  }
  for(int i = 1; i < n; i++) {
    if(i == critical || dfsParent[i] == critical) continue;
    assert(merge(i, dfsParent[i]));
    assert(ufsz[find(i)] < sizes[0].first);
  }
  for(int i = 0; i < n; i++) {
    for(int out: edges[i]) {
      if(i == critical || out == critical) continue;
      if(!merge(i, out)) continue;
      if(ufsz[find(i)] >= sizes[0].first) {
        ufcolor(i, sizes[0].first, sizes[0].second);
        assert(upColor(critical, sizes[1].first, sizes[1].second));
        fillRest(n, sizes[2].second);
        return consolidate(n);
      }
    }
  }
  vector<int> ans;
  ans.resize(n);
  return ans;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < p.size(); i++) {
                  ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 85 ms 13688 KB ok, correct split
8 Correct 81 ms 12408 KB ok, correct split
9 Correct 88 ms 11956 KB ok, correct split
10 Correct 100 ms 14016 KB ok, correct split
11 Correct 96 ms 14000 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 100 ms 12532 KB ok, correct split
5 Correct 78 ms 9424 KB ok, correct split
6 Correct 84 ms 13944 KB ok, correct split
7 Correct 88 ms 12320 KB ok, correct split
8 Correct 129 ms 11636 KB ok, correct split
9 Correct 80 ms 9336 KB ok, correct split
10 Correct 66 ms 9840 KB ok, correct split
11 Correct 69 ms 9940 KB ok, correct split
12 Correct 66 ms 9840 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB ok, correct split
2 Correct 81 ms 9424 KB ok, correct split
3 Correct 31 ms 5496 KB ok, correct split
4 Correct 20 ms 2728 KB ok, correct split
5 Correct 120 ms 11128 KB ok, correct split
6 Correct 93 ms 11128 KB ok, correct split
7 Correct 101 ms 11272 KB ok, correct split
8 Correct 102 ms 11512 KB ok, correct split
9 Correct 86 ms 11256 KB ok, correct split
10 Correct 29 ms 4984 KB ok, no valid answer
11 Correct 43 ms 6136 KB ok, no valid answer
12 Correct 77 ms 9716 KB ok, no valid answer
13 Correct 102 ms 9568 KB ok, no valid answer
14 Correct 64 ms 9760 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 5 ms 2680 KB ok, no valid answer
3 Correct 5 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2684 KB ok, correct split
6 Correct 5 ms 2680 KB ok, correct split
7 Correct 5 ms 2656 KB ok, correct split
8 Correct 4 ms 2680 KB ok, correct split
9 Correct 6 ms 2936 KB ok, correct split
10 Incorrect 6 ms 2936 KB invalid split: #1=19, #2=1848, #3=633
11 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Correct 4 ms 2680 KB ok, correct split
3 Correct 4 ms 2680 KB ok, correct split
4 Correct 4 ms 2680 KB ok, correct split
5 Correct 4 ms 2680 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 85 ms 13688 KB ok, correct split
8 Correct 81 ms 12408 KB ok, correct split
9 Correct 88 ms 11956 KB ok, correct split
10 Correct 100 ms 14016 KB ok, correct split
11 Correct 96 ms 14000 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 100 ms 12532 KB ok, correct split
16 Correct 78 ms 9424 KB ok, correct split
17 Correct 84 ms 13944 KB ok, correct split
18 Correct 88 ms 12320 KB ok, correct split
19 Correct 129 ms 11636 KB ok, correct split
20 Correct 80 ms 9336 KB ok, correct split
21 Correct 66 ms 9840 KB ok, correct split
22 Correct 69 ms 9940 KB ok, correct split
23 Correct 66 ms 9840 KB ok, correct split
24 Correct 5 ms 2680 KB ok, correct split
25 Correct 81 ms 9424 KB ok, correct split
26 Correct 31 ms 5496 KB ok, correct split
27 Correct 20 ms 2728 KB ok, correct split
28 Correct 120 ms 11128 KB ok, correct split
29 Correct 93 ms 11128 KB ok, correct split
30 Correct 101 ms 11272 KB ok, correct split
31 Correct 102 ms 11512 KB ok, correct split
32 Correct 86 ms 11256 KB ok, correct split
33 Correct 29 ms 4984 KB ok, no valid answer
34 Correct 43 ms 6136 KB ok, no valid answer
35 Correct 77 ms 9716 KB ok, no valid answer
36 Correct 102 ms 9568 KB ok, no valid answer
37 Correct 64 ms 9760 KB ok, no valid answer
38 Correct 4 ms 2680 KB ok, correct split
39 Correct 5 ms 2680 KB ok, no valid answer
40 Correct 5 ms 2680 KB ok, correct split
41 Correct 4 ms 2680 KB ok, correct split
42 Correct 4 ms 2684 KB ok, correct split
43 Correct 5 ms 2680 KB ok, correct split
44 Correct 5 ms 2656 KB ok, correct split
45 Correct 4 ms 2680 KB ok, correct split
46 Correct 6 ms 2936 KB ok, correct split
47 Incorrect 6 ms 2936 KB invalid split: #1=19, #2=1848, #3=633
48 Halted 0 ms 0 KB -