Codeforces/1829/f.cpp
Matej Focko 0bfc6f808e
1829(cpp): solve contest
* “A. Love Story”
* “B. Blank Space”
* “C. Mr. Perfectly Fine”
* “D. Gold Rush”
* “E. The Lakes”
* “F. Forewer Winter”
* “G. Hits Different”
* “H. Don't Blame Me”

Signed-off-by: Matej Focko <me@mfocko.xyz>
2023-07-23 11:33:22 +02:00

206 lines
4.1 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
template <typename T, typename U>
std::ostream &operator<<(std::ostream &s, std::pair<T, U> const &p) {
return s << p.first << " " << p.second;
}
namespace helpers {
using namespace std;
namespace math {
long pow(long base, long exp) {
if (exp == 0) return 1;
long half = pow(base, exp / 2);
if (exp % 2 == 0) return half * half;
return half * half * base;
}
} // namespace math
namespace input {
template <typename T>
std::vector<T> load_vector(std::size_t size) {
std::vector<T> result{};
for (auto i = 0u; i < size; ++i) {
T x;
std::cin >> x;
result.push_back(std::move(x));
}
return result;
}
} // namespace input
namespace output {
template <typename T>
inline void answer(const T &ans) {
cout << ans << "\n";
}
inline void yes() { cout << "YES\n"; }
inline void no() { cout << "NO\n"; }
inline void yesno(bool ans) {
if (ans) {
yes();
} else {
no();
}
}
} // namespace output
using namespace math;
using namespace input;
using namespace output;
#define LOOP(n) for (auto i = 0; i < n; ++i)
} // namespace helpers
// for N test cases, uncomment for single test case
// #define SINGLE
namespace solution {
using namespace std;
using namespace helpers;
struct vertex {
set<int> neighbours;
};
pair<int, int> determine_snowflake(const map<int, vertex> &vertices) {
map<int, int> counts;
int leaf_parent = -1;
for (const auto &mapping : vertices) {
auto v = mapping.second;
if (v.neighbours.size() == 1) {
leaf_parent = *v.neighbours.begin();
continue;
}
counts[v.neighbours.size()]++;
}
int y = vertices.at(leaf_parent).neighbours.size() - 1;
// V = 1 + x + x * y
// V - 1 = x + x * y
// V - 1 = x * (1 + y)
// x = (V - 1) / (y + 1)
int x = (vertices.size() - 1) / (y + 1);
return {x, y};
}
void solve() {
int V, E;
cin >> V >> E;
map<int, vertex> vertices;
LOOP(E) {
int u, v;
cin >> u >> v;
vertices[u].neighbours.insert(v);
vertices[v].neighbours.insert(u);
}
answer(determine_snowflake(vertices));
}
} // namespace solution
using namespace solution;
#ifdef TEST
#include "../.common/cpp/catch_amalgamated.hpp"
static map<int, vertex> edges_to_graph(vector<pair<int, int>> edges) {
map<int, vertex> vertices;
for (auto [u, v] : edges) {
vertices[u].neighbours.insert(v);
vertices[v].neighbours.insert(u);
}
return vertices;
}
TEST_CASE("examples") {
CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
{21, 20}, {21, 20}, {5, 20}, {13, 20}, {1, 3}, {11, 3},
{10, 3}, {4, 8}, {19, 8}, {14, 8}, {9, 7}, {12, 7},
{17, 7}, {18, 6}, {16, 6}, {2, 6}, {6, 15}, {7, 15},
{8, 15}, {20, 15}, {3, 15}})) == pair{5, 3});
CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
{7, 6}, {1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}})) ==
pair{2, 2});
CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
{9, 8},
{9, 3},
{3, 6},
{6, 2},
{2, 1},
{5, 2},
{2, 7},
{4, 3},
{3, 8},
})) == pair{2, 3});
CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}})) == pair{2, 2});
CHECK(determine_snowflake(edges_to_graph(vector<pair<int, int>>{
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 21}, {2, 22},
{2, 23}, {2, 24}, {3, 31}, {3, 32}, {3, 33}, {3, 34}, {4, 41},
{4, 42}, {4, 43}, {4, 44}, {5, 51}, {5, 52}, {5, 53}, {5, 54},
{6, 61}, {6, 62}, {6, 63}, {6, 64},
})) == pair{5, 4});
}
#else
int main(void) {
#ifdef SINGLE
solution::solve();
#else
// for multiple test cases
int N;
std::cin >> N >> std::ws;
for (auto i = 0; i < N; ++i) {
solution::solve();
}
#endif
return 0;
}
#endif