Submission #1181448

#TimeUsernameProblemLanguageResultExecution timeMemory
1181448jbarejaRope (JOI17_rope)C++20
100 / 100
696 ms85144 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int N; // liczba węzłów int M; // liczba kolorów vector<int> C; vector<int> ans; vector<int> cnt_color; unordered_map<ll,int> M_1; // < posortowana para, ilość > - licząc od pierwszego unordered_map<ll,int> M_2; // < posortowana para, ilość > - licząc od drugiego vector<int> with_one_1; vector<int> with_one_2; vector<int> with_any_1; vector<int> with_any_2; int cnt_pairs_1 = 0; int cnt_pairs_2 = 0; int last1 = 0; int first2 = 0; int last2 = 0; long long hsh_pair(int a, int b) { if (a > b) swap(a, b); return (ll)a + (ll)b * 1'000'007LL; } int cost(int a, int b) { int pairs_ab_1 = 0; if (M_1.contains(hsh_pair(a,b))) pairs_ab_1 = M_1[hsh_pair(a,b)]; int cost1 = with_one_1[a] + with_one_1[b] - pairs_ab_1 + 2 * (cnt_pairs_1 - with_any_1[a] - with_any_1[b] + pairs_ab_1) + (last1 != a && last1 != b && last1 != 0); int pairs_ab_2 = 0; if (M_2.contains(hsh_pair(a,b))) pairs_ab_2 = M_2[hsh_pair(a,b)]; int cost2 = with_one_2[a] + with_one_2[b] - pairs_ab_2 + 2 * (cnt_pairs_2 - with_any_2[a] - with_any_2[b] + pairs_ab_2) + (first2 != a && first2 != b && first2 != 0) + (last2 != a && last2 != b && last2 != 0); return min(cost1, cost2); } int cost_not_touching(int a, int b) { return N - cnt_color[a] - cnt_color[b]; } bool is_touching(int a, int b) { if (M_1.contains(hsh_pair(a,b)) || M_2.contains(hsh_pair(a,b))) return true; if ((C[N-1] == a && C[N] == b) || (C[N-1] == b && C[N] == a)) return true; return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; C.assign(N+2, 0); ans.assign(M+1, 0); cnt_color.assign(M+1, 0); with_one_1.assign(M+1, 0); with_one_2.assign(M+1, 0); with_any_1.assign(M+1, 0); with_any_2.assign(M+1, 0); vector<pair<int,int>> colors; // < -liczba wystąpień, kolor > for (int i=1; i<=N; i++) { cin >> C[i]; cnt_color[C[i]]++; } for (int i=1; i<=M; i++) colors.push_back({ -cnt_color[i], i }); sort(colors.begin(), colors.end()); for (int i=1; i<=M; i++) ans[i] = N - cnt_color[i]; for (int i=1; i+1<=N; i+=2) { M_1[hsh_pair( C[i], C[i+1] )]++; cnt_pairs_1++; if (C[i] == C[i+1]) with_any_1[C[i]]++; else with_one_1[C[i]]++, with_one_1[C[i+1]]++, with_any_1[C[i]]++, with_any_1[C[i+1]]++; } if (N % 2 == 1) last1 = C[N]; first2 = C[1]; for (int i=2; i+1<=N; i+=2) { M_2[hsh_pair( C[i], C[i+1] )]++; cnt_pairs_2++; if (C[i] == C[i+1]) with_any_2[C[i]] ++; else with_one_2[C[i]]++, with_one_2[C[i+1]]++, with_any_2[C[i]]++, with_any_2[C[i+1]]++; } if (N % 2 == 0) last2 = C[N]; for (int i=1; i<=N-1; i++) if (C[i] != C[i+1]) { int temp = cost(C[i],C[i+1]); ans[C[i]] = min(ans[C[i]], temp); ans[C[i+1]] = min(ans[C[i+1]], temp); } for (int i=1; i<=M; i++) { for (const auto& [cnt, c]: colors) { if (i == c || is_touching(i, c)) continue; int temp = cost_not_touching(i, c); ans[i] = min(ans[i], temp); ans[c] = min(ans[c], temp); break; } } for (int i=1; i<=M; i++) cout << ans[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...