Submission #4074904
Source Code Expand
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0, max_i = (n); i < max_i; i++) #define REPI(i, a, b) for (int i = (a), max_i = (b); i < max_i; i++) #define ALL(obj) (obj).begin(), (obj).end() #define RALL(obj) (obj).rbegin(), (obj).rend() #define fi first #define se second #define int long long using namespace std; using ll = long long; using II = pair<int, int>; using VII = vector<II>; using VVII = vector<VII>; using VI = vector<int>; using VVI = vector<VI>; using VVVI = vector<VVI>; template <class T = int> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template <class T = int> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } template <class T> ostream& operator<<(ostream &s, const vector<T>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : " "); return s; } template <class T> ostream& operator<<(ostream &s, const vector<vector<T>>& d) { REP (i, d.size()) s << d[i] << (i == d.size() - 1 ? "" : "\n"); return s; } template <class T, class S> ostream& operator<<(ostream &s, const pair<T, S>& p) { s << "{" << p.first << ", " << p.second << "}"; return s; } template <class T, class S> ostream& operator<<(ostream& s, const map<T, S> m) { for (auto it = m.begin(); it != m.end(); it++) { s << *it << (next(it) == m.end() ? "" : "\n"); } return s; } #ifdef _MY_DEBUG #define dump(...) cerr << "/* " << #__VA_ARGS__ << " :[" << __LINE__ << ":" << __FUNCTION__ << "]" << endl, dump_func(__VA_ARGS__), cerr << "*/\n\n"; #else #define dump(...) #endif void dump_func() { cerr << endl; } template <class Head, class... Tail> void dump_func(Head&& h, Tail&&... t) { cerr << h << (sizeof...(Tail) == 0 ? "" : ", "), dump_func(forward<Tail>(t)...); } struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); } } fast; constexpr int MOD = 1e9 + 7; using VB = vector<bitset<40>>; VB rm_nei(const VB& g, int v) { int n = g.size(); VB ret; int i0 = 0; REP (i, n) { if (i == v || g[v][i]) continue; ret.push_back(0); int j0 = 0; REP (j, n) { if (j == v || g[v][j]) continue; ret[i0][j0] = g[i][j]; j0++; } i0++; } return ret; } int solve(VB& g) { int n = g.size(); if (n == 0) return 0; int mi = 1e18; int v = -1; REP (i, n) { int deg = g[i].count(); if (deg < mi) { mi = deg; v = i; } } VI cans = {v}; REP (i, n) { if (g[v][i]) cans.push_back(i); } int ans = 0; for (int i: cans) { VB new_g = rm_nei(g, i); ans = max(ans, 1 + solve(new_g)); } return ans; } signed main() { int n, m; cin >> n >> m; VB g(n); REP (i, m) { int a, b; cin >> a >> b; a--; b--; g[a][b] = 1; g[b][a] = 1; } cout << solve(g) << endl; }
Submission Info
Submission Time | |
---|---|
Task | G - Mixture Drug |
User | knshnb |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 2854 Byte |
Status | AC |
Exec Time | 341 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 1 ms | 256 KB |
subtask_1_10.txt | AC | 33 ms | 256 KB |
subtask_1_11.txt | AC | 1 ms | 256 KB |
subtask_1_12.txt | AC | 107 ms | 256 KB |
subtask_1_13.txt | AC | 1 ms | 256 KB |
subtask_1_14.txt | AC | 1 ms | 256 KB |
subtask_1_15.txt | AC | 1 ms | 256 KB |
subtask_1_16.txt | AC | 2 ms | 256 KB |
subtask_1_17.txt | AC | 2 ms | 256 KB |
subtask_1_18.txt | AC | 2 ms | 256 KB |
subtask_1_19.txt | AC | 1 ms | 256 KB |
subtask_1_2.txt | AC | 1 ms | 256 KB |
subtask_1_20.txt | AC | 1 ms | 256 KB |
subtask_1_21.txt | AC | 1 ms | 256 KB |
subtask_1_22.txt | AC | 2 ms | 256 KB |
subtask_1_23.txt | AC | 1 ms | 256 KB |
subtask_1_24.txt | AC | 5 ms | 256 KB |
subtask_1_25.txt | AC | 292 ms | 256 KB |
subtask_1_26.txt | AC | 341 ms | 256 KB |
subtask_1_27.txt | AC | 58 ms | 256 KB |
subtask_1_28.txt | AC | 3 ms | 256 KB |
subtask_1_29.txt | AC | 1 ms | 256 KB |
subtask_1_3.txt | AC | 1 ms | 256 KB |
subtask_1_30.txt | AC | 1 ms | 256 KB |
subtask_1_31.txt | AC | 1 ms | 256 KB |
subtask_1_32.txt | AC | 1 ms | 256 KB |
subtask_1_33.txt | AC | 1 ms | 256 KB |
subtask_1_34.txt | AC | 2 ms | 256 KB |
subtask_1_35.txt | AC | 7 ms | 256 KB |
subtask_1_36.txt | AC | 4 ms | 256 KB |
subtask_1_37.txt | AC | 1 ms | 256 KB |
subtask_1_38.txt | AC | 1 ms | 256 KB |
subtask_1_39.txt | AC | 1 ms | 256 KB |
subtask_1_4.txt | AC | 1 ms | 256 KB |
subtask_1_40.txt | AC | 1 ms | 256 KB |
subtask_1_41.txt | AC | 1 ms | 256 KB |
subtask_1_42.txt | AC | 1 ms | 256 KB |
subtask_1_43.txt | AC | 1 ms | 256 KB |
subtask_1_44.txt | AC | 1 ms | 256 KB |
subtask_1_45.txt | AC | 1 ms | 256 KB |
subtask_1_46.txt | AC | 1 ms | 256 KB |
subtask_1_47.txt | AC | 1 ms | 256 KB |
subtask_1_48.txt | AC | 1 ms | 256 KB |
subtask_1_5.txt | AC | 15 ms | 256 KB |
subtask_1_6.txt | AC | 44 ms | 256 KB |
subtask_1_7.txt | AC | 16 ms | 256 KB |
subtask_1_8.txt | AC | 34 ms | 256 KB |
subtask_1_9.txt | AC | 19 ms | 256 KB |