Submission #1097162

#TimeUsernameProblemLanguageResultExecution timeMemory
1097162gygHexagonal Territory (APIO21_hexagon)C++17
12 / 100
921 ms1048576 KiB
#include "hexagon.h" #include <bits/stdc++.h> using namespace std; #define lint long long #define arr array #define vct vector #define hmap unordered_map #define hset unordered_set #define pll pair<lint, lint> #define fir first #define sec second #define lb lower_bound const lint MD = 1e9 + 7, N_NDS = 1e6 + 5, INF = 1e18, INV = 5e8 + 4; lint n, a, b; vct<lint> drc, lng; lint md(lint x) { return (x + MD) % MD; } pll mv(pll pt, lint drc, lint lng) { pll dlt; if (drc == 1) dlt = {0, 1}; if (drc == 2) dlt = {1, 1}; if (drc == 3) dlt = {1, 0}; if (drc == 4) dlt = {0, -1}; if (drc == 5) dlt = {-1, -1}; if (drc == 6) dlt = {-1, 0}; return {pt.fir + dlt.fir * lng, pt.sec + dlt.sec * lng}; } vct<pll> gt_pts() { pll pt = {0, 0}; vct<pll> ans; for (int i = 0; i < n; i++) { for (int j = 0; j < lng[i]; j++) { pt = mv(pt, drc[i], 1); ans.push_back(pt); } } return ans; } vct<pll> nghbrs(pll pt) { vct<pll> ans; for (int i = 1; i <= 6; i++) ans.push_back(mv(pt, i, 1)); return ans; } set<pll> pt_nds, pth_nds, vs; void dfs(pll pt) { vs.insert(pt); for (pll nw_pt : nghbrs(pt)) if (pt_nds.count(nw_pt) && !vs.count(nw_pt) && !pth_nds.count(nw_pt)) dfs(nw_pt); } hmap<lint, vct<pll>> clmns; int n_nds; arr<lint, N_NDS> x; arr<pll, N_NDS> y; lint prcmp1() { vct<pll> pts = gt_pts(); for (pll pt : pts) { pt_nds.insert(pt), pth_nds.insert(pt); for (pll nw_pt : nghbrs(pt)) pt_nds.insert(nw_pt); } pll mn_x; for (pll pt : pt_nds) mn_x = min(mn_x, pt); dfs(mn_x); for (pll pt : pts) clmns[pt.fir].push_back(pt); for (pair<lint, vct<pll>> clmn : clmns) { sort(clmn.sec.begin(), clmn.sec.end()); for (pll pt : clmn.sec) { if (vs.count({pt.fir, pt.sec - 1})) n_nds++, x[n_nds] = clmn.fir, y[n_nds] = {pt.sec, 0}; if (vs.count({pt.fir, pt.sec + 1})) y[n_nds].sec = pt.sec; } } // for (int u = 1; u <= n_nds; u++) { // cout << u << ": " << x[u] << " " << y[u].fir << " " << y[u].sec << endl; // } lint ans = 0; for (int u = 1; u <= n_nds; u++) ans += y[u].sec - y[u].fir + 1; return ans; } hmap<lint, map<pll, int>> nd; hmap<lint, set<pll>> ys; arr<vct<int>, N_NDS> adj; int rt; arr<lint, N_NDS> lw; arr<pll, N_NDS> rng; arr<bool, N_NDS> sn; void dfs2(int u) { sn[u] = true; for (int v : adj[u]) { if (sn[v]) continue; pll intr = {max(rng[u].fir, y[v].fir), min(rng[u].sec + 1, y[v].sec)}; if (intr.fir <= intr.sec) rng[v] = intr, lw[v] = lw[u] + 1; else if (rng[u].sec < y[v].fir) rng[v] = {y[v].fir, y[v].fir}, lw[v] = lw[u] + y[v].fir - rng[u].sec + 1; else { assert(y[v].sec < rng[u].fir); rng[v] = {y[v].sec, y[v].sec}, lw[v] = lw[u] + rng[u].fir - y[v].sec + 1; } dfs2(v); } } void prcmp2() { for (int u = 1; u <= n_nds; u++) nd[x[u]][y[u]] = u, ys[x[u]].insert(y[u]); for (int u = 1; u <= n_nds; u++) { for (lint nw_x : {x[u] - 1, x[u] + 1}) { auto it1 = ys[nw_x].lb({y[u].fir, -INF}); if (it1 != ys[nw_x].begin()) if (next(it1, -1)->sec >= y[u].fir) adj[u].push_back(nd[nw_x][*next(it1, -1)]); for (auto it2 = it1; it2 != ys[nw_x].end() && it2->fir <= y[u].sec; it2++) adj[u].push_back(nd[nw_x][*it2]); } } rt = nd[0][*next(ys[0].lb({1, -1}), -1)]; lw[rt] = 0, rng[rt] = {0, 0}; dfs2(rt); // cout << y[rt].fir << " " << y[rt].sec << endl; // for (int u = 1; u <= n_nds; u++) { // cout << x[u] << "," << y[u].fir << "," << y[u].sec << ": "; // for (int v : adj[u]) cout << x[v] << "," << y[v].fir << "," << y[v].sec << " "; // // for (int v : adj[u]) cout << v << " "; // cout << endl; // } } lint sm(lint x, lint y) { if (x > y) return 0; return md(md(md(x + y) * md(y - x + 1)) * INV); } int draw_territory(int _n, int _a, int _b, vct<int> _drc, vct<int> _lng) { n = _n, a = _a, b = _b; for (int i = 0; i < n; i++) drc.push_back(_drc[i]), lng.push_back(_lng[i]); lint ar = prcmp1(); lint ans = md(ar * a); prcmp2(); // for (int u = 1; u <= n_nds; u++) { // cout << x[u] << "," << y[u].fir << "," << y[u].sec << ": " << lw[u] << "," << rng[u].fir << "," << rng[u].sec << endl; // } for (int u = 1; u <= n_nds; u++) { lint inc_ans = md(b * md(lw[u] * (rng[u].sec - rng[u].fir + 1) + sm(lw[u] + 1, lw[u] + rng[u].fir - y[u].fir) + sm(lw[u] + 1, lw[u] + y[u].sec - rng[u].sec))); ans = md(ans + inc_ans); } return ans; }
#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...