#include <iostream> #include <vector> #include <algorithm> #include <unordered_set> void test() { using namespace std; int n, m, k; cin >> n >> m >> k; vector<vector<int>> connections1(n, vector<int>()); vector<vector<int>> connections2(n, vector<int>()); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; connections1[a-1].push_back(b-1); connections2[b-1].push_back(a-1); } vector<int> degrees1(n, 1); vector<int> degrees2(n, 1); for (int i = 0; i < n; ++i) { for (int j : connections1[i]) degrees1[j] = max(degrees1[j], degrees1[i]+1); } for (int i = n-1; i >= 0; --i) { for (int j : connections2[i]) degrees2[j] = max(degrees2[j], degrees2[i]+1); } int cutoff = 0; vector<int> subset; subset.reserve(n); while (true) { subset.clear(); for (int i = 0; i < n; ++i) if (degrees1[i] > cutoff && degrees2[i] > cutoff) subset.push_back(i); //cerr << "reduced to " << subset.size() << endl; if (subset.size() < 60) break; ++cutoff; } const int S = (int) subset.size(); if (S < k) { cout << -1 << endl; return; } bool valid = true; vector<int> idx(k); for (int i = 0; i < k; ++i) idx[i] = i; auto advance = [&]() { for (int i = k-1; i >= 0; --i) { idx[i] += 1; for (int j = 1; i+j < k; ++j) idx[i+j] = idx[i]+j; if (idx[k-1] < S-1) return; } valid = false; }; vector<int> degrees(n); int answer = n; while(valid) { fill(degrees.begin(), degrees.end(), 1); for (auto i : idx) degrees[subset[i]] = 0; //cerr << "Testing without: "; //for (auto i : idx) cerr << subset[i] << ' '; cerr << endl; int highest = 0; for (int i = 0; i < n; ++i) { highest = max(highest, degrees[i]); for (int j : connections1[i]) { if (degrees[j] == 0) continue; degrees[j] = max(degrees[j], degrees[i]+1); } } //cerr << "score = " << highest << endl; answer = min(answer, highest); advance(); } cout << answer << endl; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); test(); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> void test() { using namespace std; int n, m, k; cin >> n >> m >> k; vector<vector<int>> connections1(n, vector<int>()); vector<vector<int>> connections2(n, vector<int>()); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; connections1[a-1].push_back(b-1); connections2[b-1].push_back(a-1); } vector<int> degrees1(n, 1); vector<int> degrees2(n, 1); for (int i = 0; i < n; ++i) { for (int j : connections1[i]) degrees1[j] = max(degrees1[j], degrees1[i]+1); } for (int i = n-1; i >= 0; --i) { for (int j : connections2[i]) degrees2[j] = max(degrees2[j], degrees2[i]+1); } int cutoff = 0; vector<int> subset; subset.reserve(n); while (true) { subset.clear(); for (int i = 0; i < n; ++i) if (degrees1[i] > cutoff && degrees2[i] > cutoff) subset.push_back(i); //cerr << "reduced to " << subset.size() << endl; if (subset.size() < 60) break; ++cutoff; } const int S = (int) subset.size(); if (S < k) { cout << -1 << endl; return; } bool valid = true; vector<int> idx(k); for (int i = 0; i < k; ++i) idx[i] = i; auto advance = [&]() { for (int i = k-1; i >= 0; --i) { idx[i] += 1; for (int j = 1; i+j < k; ++j) idx[i+j] = idx[i]+j; if (idx[k-1] < S-1) return; } valid = false; }; vector<int> degrees(n); int answer = n; while(valid) { fill(degrees.begin(), degrees.end(), 1); for (auto i : idx) degrees[subset[i]] = 0; //cerr << "Testing without: "; //for (auto i : idx) cerr << subset[i] << ' '; cerr << endl; int highest = 0; for (int i = 0; i < n; ++i) { highest = max(highest, degrees[i]); for (int j : connections1[i]) { if (degrees[j] == 0) continue; degrees[j] = max(degrees[j], degrees[i]+1); } } //cerr << "score = " << highest << endl; answer = min(answer, highest); advance(); } cout << answer << endl; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); test(); return 0; } |