結果
問題 | No.2677 Minmax Independent Set |
ユーザー |
![]() |
提出日時 | 2024-02-29 21:58:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,377 bytes |
コンパイル時間 | 1,316 ms |
コンパイル使用メモリ | 136,488 KB |
最終ジャッジ日時 | 2025-02-19 22:05:17 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 WA * 52 |
ソースコード
#include <iostream>#include <iomanip>#include <fstream>#include <string>#include <array>#include <vector>#include <deque>#include <list>#include <set>#include <map>#include <unordered_map>#include <unordered_set>#include <stack>#include <queue>#include <bitset>#include <tuple>#include <cmath>#include <complex>#include <algorithm>#include <utility>#include <regex>#include <cstdint>#include <numeric>#include <functional>#include <cassert>using namespace std;namespace utils{#define ALL(x) begin(x), end(x)#define RALL(x) rbegin(x), rend(x)///----- aliasesusing ll = long long int;using ull = unsigned long long;template<class T, class Compare> using p_queue = priority_queue<T, vector<T>, Compare>;template<class T> using min_queue = p_queue<T, greater<T>>;template<class T> using max_queue = p_queue<T, less<T>>;template<class T> inline bool CHMIN(T& X, const T& A){ if(X > A) {X = A; return true;} return false; }template<class T> inline bool CHMAX(T& X, const T& A){ if(X < A) {X = A; return true;} return false; }///----- vector I/Otemplate<class T>vector<T> VEC(size_t n, T t){return vector<T>(n, t);}template<class ...Ts>auto VEC(size_t n, Ts ... ts){return vector<decltype(VEC(ts...))>(n, VEC(ts...));}template<class T>istream& operator>>(istream& is, vector<T>& v){for (auto &&x : v) { is >> x; } return is;}template<class T>ostream& operator<<(ostream& os, const vector<T>& v){auto p = v.begin();assert(p != v.end());os << *p++;while(p != v.end()){os << ' ' << *p++;}return os ;}template<class T>ostream& operator<<(ostream& os, const vector<vector<T>>& v){auto p = v.begin();assert(p != v.end());os << *p++;while(p != v.end()){os << '\n' << *p++;}return os;}///----- tuple I/Otemplate <class S, class T>istream& operator>>(istream& is, tuple<S, T>& t){return is >> get<0>(t) >> get<1>(t);}template <class S, class T>istream& operator>>(istream& is, pair<S, T>& t){return is >> get<0>(t) >> get<1>(t);}template <class S, class T, class U>istream& operator>>(istream& is, tuple<S, T, U>& t){return is >> get<0>(t) >> get<1>(t) >> get<2>(t);}template <class S, class T>ostream& operator<<(ostream& os, const tuple<S, T>& t){return os << get<0>(t) << ' ' << get<1>(t);}template <class S, class T>ostream& operator<<(ostream& os, const pair<S, T>& t){return os << get<0>(t) << ' ' << get<1>(t);}template <class S, class T, class U>ostream& operator<<(ostream& os, const tuple<S, T, U>& t){return os << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t);}///----- constantsconstexpr ll INFLL = 1'000'000'000'000'000'020ll;constexpr ll INF = 1'000'000'009;constexpr double PI = 3.14'159'265'358'979'323'846;constexpr double EPS = 1e-12;}using namespace utils;class solver{istream& is;ostream& os;public:solver(istream& I, ostream& O) :is(I), os(O) {}int N;vector<vector<int>> E;bool input() {is >> N;E.resize(N);for (int i = 0; i < N - 1; ++i) {int a, b;is >> a >> b;a--; b--;E[b].push_back(a);E[a].push_back(b);} // end ireturn !!is;}void run();};void solver::run(){if(!input()) return;int max_deg = accumulate(ALL(E), 0, [](int a, vector<int>& b){return max<int>(a, b.size());});os << N - max_deg << endl;}int main(int argc, char *argv[]) {cin.tie(nullptr);ios::sync_with_stdio(false);cout << setprecision(16) << scientific;#ifdef XELMHstring test_cases = "test_g.txt";cerr << test_cases << " -->" << endl;auto fs = fstream(test_cases, fstream::in);int loop = 0;while(fs) {loop++;cout << '#' << loop << "#------\n";solver(fs, cout).run();}if(loop <= 1) {cout << "===" << endl;while(cin) solver(cin, cout).run();}#elsesolver(cin, cout).run();#endifreturn 0;}