Submission #1063718

#TimeUsernameProblemLanguageResultExecution timeMemory
1063718aaaaaarrozSplit the Attractions (IOI19_split)C++17
0 / 100
0 ms348 KiB
#include "split.h" #include<bits/stdc++.h> using namespace std; vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { vector<vector<int>> graph(n); for (int i = 0; i < q.size(); i++) { graph[p[i]].push_back(q[i]); graph[q[i]].push_back(p[i]); } vector<int> ans(n, 0); vector<int> component(n, -1); vector<int> size; function<void(int, int)> dfs = [&](int u, int comp_id) { component[u] = comp_id; size[comp_id]++; for (int v : graph[u]) { if (component[v] == -1) { dfs(v, comp_id); } } }; int comp_count = 0; for (int i = 0; i < n; i++) { if (component[i] == -1) { size.push_back(0); dfs(i, comp_count++); } } vector<int> order(comp_count); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int x, int y) { return size[x] > size[y]; }); if (size[order[0]] >= b + c) { int remaining = b + c; queue<int> q; q.push(-1); for (int i = 0; i < n; i++) { if (component[i] == order[0]) { if (remaining > c) { ans[i] = 2; remaining--; } else { ans[i] = 3; } } } if (remaining != 0) { return vector<int>(n, 0); } } else { int remaining_b = b, remaining_c = c; for (int id : order) { if (size[id] <= remaining_b && remaining_b > 0) { for (int i = 0; i < n; i++) { if (component[i] == id) { ans[i] = 2; remaining_b--; } } } else { for (int i = 0; i < n; i++) { if (component[i] == id && remaining_c > 0) { ans[i] = 3; remaining_c--; } } } } if (remaining_b != 0 || remaining_c != 0) { return vector<int>(n, 0); } } int remaining_a = a; for (int i = 0; i < n; i++) { if (ans[i] == 0 && remaining_a > 0) { ans[i] = 1; remaining_a--; } } if (remaining_a != 0) { return vector<int>(n, 0); } return ans; }

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < q.size(); i++) {
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...