結果
問題 | No.2677 Minmax Independent Set |
ユーザー |
![]() |
提出日時 | 2024-02-29 21:58:59 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,377 bytes |
コンパイル時間 | 1,701 ms |
コンパイル使用メモリ | 142,400 KB |
実行使用メモリ | 15,172 KB |
最終ジャッジ日時 | 2024-09-30 00:10:15 |
合計ジャッジ時間 | 7,136 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 78 ms
15,032 KB |
testcase_29 | WA | - |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | AC | 30 ms
7,768 KB |
testcase_51 | AC | 4 ms
5,248 KB |
testcase_52 | AC | 70 ms
12,948 KB |
testcase_53 | AC | 62 ms
12,004 KB |
testcase_54 | AC | 4 ms
5,248 KB |
testcase_55 | WA | - |
testcase_56 | WA | - |
testcase_57 | WA | - |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | WA | - |
testcase_61 | WA | - |
testcase_62 | WA | - |
testcase_63 | WA | - |
ソースコード
#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) ///----- aliases using 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/O template<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/O template <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); } ///----- constants constexpr 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 i return !!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 XELMH string 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(); } #else solver(cin, cout).run(); #endif return 0; }