oj.uz

Submission #144374

# Submission time Handle Problem Language Result Execution time Memory
144374 2019-08-16T18:39:36 Z xiaowuc1 Split the Attractions (IOI19_split) C++14
18 / 100
 123 ms 16764 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]);
    ans.push_back(ret[i]);
  }
  return ans;
}

void downColor(int curr, int par, int& need, int want) {
  ret[curr] = want;
  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);
    }
  }
  // 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:103: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 5 ms 2680 KB ok, correct split
4 Correct 5 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 116 ms 13712 KB ok, correct split
8 Correct 86 ms 12408 KB ok, correct split
9 Correct 92 ms 12024 KB ok, correct split
10 Correct 118 ms 13944 KB ok, correct split
11 Correct 104 ms 13944 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 5 ms 2680 KB ok, correct split
4 Correct 108 ms 12640 KB ok, correct split
5 Correct 80 ms 9336 KB ok, correct split
6 Correct 85 ms 13944 KB ok, correct split
7 Correct 106 ms 12304 KB ok, correct split
8 Correct 123 ms 11788 KB ok, correct split
9 Correct 81 ms 9332 KB ok, correct split
10 Correct 63 ms 9840 KB ok, correct split
11 Correct 64 ms 9840 KB ok, correct split
12 Correct 75 ms 9768 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB ok, correct split
2 Runtime error 71 ms 16764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB ok, correct split
2 Correct 4 ms 2684 KB ok, no valid answer
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 4 ms 2680 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 5 ms 2680 KB ok, correct split
4 Correct 5 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 116 ms 13712 KB ok, correct split
8 Correct 86 ms 12408 KB ok, correct split
9 Correct 92 ms 12024 KB ok, correct split
10 Correct 118 ms 13944 KB ok, correct split
11 Correct 104 ms 13944 KB ok, correct split
12 Correct 4 ms 2680 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 5 ms 2680 KB ok, correct split
15 Correct 108 ms 12640 KB ok, correct split
16 Correct 80 ms 9336 KB ok, correct split
17 Correct 85 ms 13944 KB ok, correct split
18 Correct 106 ms 12304 KB ok, correct split
19 Correct 123 ms 11788 KB ok, correct split
20 Correct 81 ms 9332 KB ok, correct split
21 Correct 63 ms 9840 KB ok, correct split
22 Correct 64 ms 9840 KB ok, correct split
23 Correct 75 ms 9768 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Runtime error 71 ms 16764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -