oj.uz

Submission #144408

# Submission time Handle Problem Language Result Execution time Memory
144408 2019-08-16T20:21:35 Z xiaowuc1 Split the Attractions (IOI19_split) C++14
18 / 100
 130 ms 14160 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;
  map<int, int> dp;
  for(int i = 0; i < n; i++) {
    assert(ret[i] >= 1 && ret[i] <= 3);
    ans.push_back(ret[i]);
    dp[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(need == 0) break;
    if(dfsParent[out] != curr) 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:107: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 2684 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 90 ms 13844 KB ok, correct split
8 Correct 85 ms 12408 KB ok, correct split
9 Correct 94 ms 12024 KB ok, correct split
10 Correct 120 ms 13944 KB ok, correct split
11 Correct 95 ms 14160 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 106 ms 12660 KB ok, correct split
5 Correct 88 ms 9464 KB ok, correct split
6 Correct 104 ms 13984 KB ok, correct split
7 Correct 93 ms 12252 KB ok, correct split
8 Correct 130 ms 11640 KB ok, correct split
9 Correct 100 ms 9436 KB ok, correct split
10 Correct 64 ms 9840 KB ok, correct split
11 Correct 66 ms 9840 KB ok, correct split
12 Correct 67 ms 9840 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 Incorrect 83 ms 9400 KB invalid split: #1=19999, #2=40000, #3=40001
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 5 ms 2684 KB ok, correct split
6 Correct 4 ms 2680 KB ok, correct split
7 Correct 5 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 Correct 6 ms 2936 KB ok, correct split
11 Correct 4 ms 2680 KB ok, correct split
12 Correct 6 ms 2936 KB ok, correct split
13 Correct 4 ms 2680 KB ok, correct split
14 Correct 4 ms 2680 KB ok, correct split
15 Correct 4 ms 2680 KB ok, correct split
16 Correct 4 ms 2680 KB ok, correct split
17 Correct 4 ms 2680 KB ok, correct split
18 Correct 4 ms 2680 KB ok, correct split
19 Correct 4 ms 2680 KB ok, correct split
20 Correct 5 ms 2808 KB ok, correct split
21 Correct 5 ms 2936 KB ok, correct split
22 Incorrect 6 ms 2936 KB invalid split: #1=799, #2=850, #3=851
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 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 90 ms 13844 KB ok, correct split
8 Correct 85 ms 12408 KB ok, correct split
9 Correct 94 ms 12024 KB ok, correct split
10 Correct 120 ms 13944 KB ok, correct split
11 Correct 95 ms 14160 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 106 ms 12660 KB ok, correct split
16 Correct 88 ms 9464 KB ok, correct split
17 Correct 104 ms 13984 KB ok, correct split
18 Correct 93 ms 12252 KB ok, correct split
19 Correct 130 ms 11640 KB ok, correct split
20 Correct 100 ms 9436 KB ok, correct split
21 Correct 64 ms 9840 KB ok, correct split
22 Correct 66 ms 9840 KB ok, correct split
23 Correct 67 ms 9840 KB ok, correct split
24 Correct 4 ms 2680 KB ok, correct split
25 Incorrect 83 ms 9400 KB invalid split: #1=19999, #2=40000, #3=40001
26 Halted 0 ms 0 KB -