Submission #1182423

#TimeUsernameProblemLanguageResultExecution timeMemory
1182423jerzykRoad Service 2 (JOI24_ho_t5)C++20
0 / 100
42 ms13636 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000'000'000'000'000'000LL; const int II = 2'000'000'000; const ll M = 1000'000'007LL; const int N = 1<<18; int tab[N], cst[N], lst1[N], whend[N]; int fau[N], l[N], r[N], h[N]; int czy[N]; vector<int> aktz; int pos[N]; pair<int, int> ran[N]; int akt[N]; int k = 0; vector<pair<int, int>> dp[N]; int Find(int a) { if(fau[a] == a) return a; return (fau[a] = Find(fau[a])); } void Union(int a, int b) { fau[Find(b)] = Find(a); } void DoR(int n, int m) { vector<pair<pair<int, int>, int>> aktr; for(int i = 1; i <= n * m; ++i) { if(fau[i] != i) continue; aktr.pb(make_pair(make_pair(r[i], l[i]), i)); whend[l[i]] = max(whend[l[i]], r[i]); } for(int i = 1; i <= n; ++i) whend[i] = max(whend[i], whend[i - 1]); sort(aktr.begin(), aktr.end()); k = (int)aktr.size(); for(int i = 1; i <= k; ++i) { ran[i] = aktr[i - 1].st; swap(ran[i].st, ran[i].nd); pos[aktr[i - 1].nd] = i; } } int BS(int q, int x) { int p = 1, k = q, s; while(p < k) { s = (p + k + 1) / 2; if(ran[akt[s]].st <= x) p = s; else k = s - 1; } return p + 1; } void Do(int i, pair<int, int> cur, int q) { int v = akt[i], l1 = cur.nd, l2 = cur.nd, dod = 1; while(l1 < ran[v].st) { ++dod; int nl1 = max(l2, whend[lst1[l1]]), nl2 = max(whend[l1], whend[lst1[l2]]); if(l1 >= nl1 && l2 >= nl2) return; l1 = nl1; l2 = nl2; } //cout << "H: " << cur.st << " " << cur.nd << "\n"; //cout << l1 << " " << l2 << " " << dod << " " << lst1[l1] << " " << BS(q, lst1[l1]) << "\n"; l1 = min(l1, ran[v].nd); l2 = min(l2, ran[v].nd); if(lst1[l1] >= ran[v].st) dp[BS(q, lst1[l1])].pb(make_pair(cur.st + dod - 1 + 1, whend[lst1[l1]])); dp[BS(q, l1)].pb(make_pair(cur.st + dod - 1 + 2, whend[l1])); if(lst1[l2] >= ran[v].st) dp[BS(q, lst1[l2])].pb(make_pair(cur.st + dod + 1, whend[lst1[l2]])); dp[BS(q, l2)].pb(make_pair(cur.st + dod + 2, whend[l2])); } void DoQ(int n, int m) { int a, b, il, q = 0; cin >> il; for(int i = 1; i <= il; ++i) { cin >> a >> b; int x = (a - 1) * m + b; x = Find(x); if(czy[x]) continue; czy[x] = 1; aktz.pb(x); ++q; akt[q] = pos[x]; } for(int i = 0; i < (int)aktz.size(); ++i) czy[aktz[i]] = 0; aktz.clear(); if(q == 1) { cout << 0 << "\n"; return; } sort(akt + 1, akt + 1 + q); int xd = 0; for(int i = 1; i <= q; ++i) if(ran[akt[i]].st > xd) { xd = ran[akt[i]].st; aktz.pb(akt[i]); } q = (int)aktz.size(); for(int i = 1; i <= q; ++i) akt[i] = aktz[i - 1]; aktz.clear(); //cout << "\nQ:\n"; //for(int i = 1; i <= q; ++i) //cout << ran[akt[i]].st << " " << ran[akt[i]].nd << "\n"; dp[1].pb(make_pair(0, ran[akt[1]].nd)); for(int i = 1; i <= q; ++i) { sort(dp[i].begin(), dp[i].end()); if((int)dp[i].size() == 0) continue; pair<int, int> a1 = dp[i][0], a2; int j = 0; while(j < (int)dp[i].size() - 1 && dp[i][j + 1].st == a1.st) ++j; a1 = dp[i][j]; while(j < (int)dp[i].size() - 1 && dp[i][j + 1].st == a1.st + 1) ++j; a2 = dp[i][j]; //cout << "C1: " << a1.st << " " << a1.nd << " | C2: " << a2.st << " " << a2.nd << "\n"; Do(i, a1, q); Do(i, a2, q); dp[i].clear(); } sort(dp[q + 1].begin(), dp[q + 1].end()); if((int)dp[q + 1].size() == 0) cout << -1 << "\n"; else cout << dp[q + 1][0].st << "\n"; dp[q + 1].clear(); } void Solve() { int n, m, q; char z; cin >> n >> m >> q; for(int i = 1; i <= n * m; ++i) {fau[i] = i; l[i] = n * m + 1; r[i] = 0;} for(int i = 1; i <= n; ++i) for(int j = 1; j < m; ++j) { cin >> z; if(z == '1') Union((i - 1) * m + j, (i - 1) * m + j + 1); } for(int i = 1; i < n; ++i) for(int j = 1; j <= m; ++j) { cin >> z; if(z == '1') Union((i - 1) * m + j, (i - 1) * m + j + m); } for(int i = 1; i <= n; ++i) { cin >> cst[i]; lst1[i] = lst1[i - 1]; if(cst[i] == 1) lst1[i] = i; } for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) { int x = (i - 1) * m + j; x = Find(x); l[x] = min(l[x], i); r[x] = max(r[x], i); h[x] = max(h[x], j); } DoR(n, m); for(int i = 1; i <= q; ++i) DoQ(n, m); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //int t; cin >> t; //while(t--) Solve(); return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...