oj.uz

Submission #295477

# Submission time Handle Problem Language Result Execution time Memory
295477 2020-09-09T17:06:03 Z tzero Split the Attractions (IOI19_split) C++14
0 / 100
 1 ms 384 KB 
#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
#include <cassert>
using namespace std;
vector<vector<int> > adj;
vector<int> sub, ans;

int dfs(int a, int p) {
  sub[a] = 0;
  for(int b : adj[a]) if(b != p) {
    sub[a] += dfs(b, a);
  }
  return sub[a];
}

void dfs2(int a, vector<int> & ans, int color) {
  ans[a] = color;
  for(int b : adj[a]) if(sub[b] < sub[a]) {
    dfs2(b, ans, color);
  }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
  adj.resize(n);
  ans.assign(n, 0);

  for(int i = 0; i < (int)p.size(); i++) {
    adj[p[i]].push_back(q[i]);
    adj[q[i]].push_back(p[i]);
  }

  bool two_endpoints = true;
  for(int i = 0; i < n; i++) {
    if(adj[i].size() > 2) two_endpoints = false;
  }

  vector<pair<int,int> > colors;
  colors.push_back(make_pair(a, 1));
  colors.push_back(make_pair(b, 2));
  colors.push_back(make_pair(c, 3));
  sort(colors.begin(), colors.end());

  if(two_endpoints) {
    for(int i = 0; i < n; i++) {
      if(a > 0) { ans[i] = 1; a--; } 
      else if(b > 0) { ans[i] = 2; b--; }
      else if(c > 0) { ans[i] = 3; c--; }
    }

    return ans;

  } else if(p.size() == n - 1) { // tree
    sub.resize(n);
    dfs(0, 0);  

    int possible = -1;
    int smallest = colors[0].first;
    int medium = colors[1].first;

    for(int i = 0; i < n && possible == -1; i++) {
      if(sub[i] >= smallest && n - sub[i] >= medium) {
        possible = i;
      } else if(sub[i] >= medium && n - sub[i] >= smallest) {
        assert(false); // Why the fuck would this happen?
        possible = i;
      }
    }

    if(possible != -1) {
      dfs2(possible, ans, colors[0].second);  
      dfs2(possible, ans, colors[1].second);
      for(int i = 0; i < n; i++) if(ans[i] == 0) {
        ans[i] = colors[2].second;  
      }
    }

    return ans;

  } else if(true || a == 1) {
    return ans;
  }
}

int _main() {
  int n, m, a, b, c;
  cin >> n >> m >> a >> b >> c;

  vector<int> p(m), pp(m);
  for(int i = 0; i < m; i++) {
    cin >> p[i] >> pp[i];
  }

  vector<int> _ans = find_split(n, a, b, c, p, pp);
  for(int x : _ans) {
    cout << x << " ";
  }
  cout << endl;

  return 0;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:54:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |   } else if(p.size() == n - 1) { // tree
      |             ~~~~~~~~~^~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Correct 0 ms 256 KB ok, correct split
5 Correct 1 ms 256 KB ok, correct split
6 Incorrect 1 ms 256 KB 3 components are not connected
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 1 ms 384 KB ok, correct split
3 Incorrect 0 ms 256 KB jury found a solution, contestant did not
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 0 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Correct 0 ms 256 KB ok, correct split
5 Correct 1 ms 256 KB ok, correct split
6 Incorrect 1 ms 256 KB 3 components are not connected
7 Halted 0 ms 0 KB -