Submission #707275

#TimeUsernameProblemLanguageResultExecution timeMemory
707275StickfishRobot (JOI21_ho_t4)C++17
34 / 100
807 ms156108 KiB
#include <iostream> #include <algorithm> #include <bitset> #include <set> #include <map> #include <vector> using namespace std; using ll = long long; const int MAXN = 1e6 + 123; const ll INF = 1e18 + 177013; vector<pair<int, ll>> edg[MAXN]; vector<pair<int, pair<int, int>>> edg_init[MAXN]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin >> n >> m; vector<pair<pair<int, int>, pair<int, int>>> edges; for (int i = 0; i < m; ++i) { int a, b, c, p; cin >> a >> b >> c >> p; --a, --b; edges.push_back({{c, p}, {a, b}}); edg_init[a].push_back({c, {b, p}}); edg_init[b].push_back({c, {a, p}}); } int sz = 0; vector<int> tin(n); vector<int> tin_cl(n); vector<vector<int>> clrs(n); vector<vector<ll>> clrssm(n); vector<vector<ll>> clrsmx(n); for (int v = 0; v < n; ++v) { sort(edg_init[v].begin(), edg_init[v].end()); tin[v] = sz; tin_cl[v] = tin[v] + edg_init[v].size() + 1; for (auto e : edg_init[v]) { clrs[v].push_back(e.first); } clrs[v].resize(unique(clrs[v].begin(), clrs[v].end()) - clrs[v].begin()); clrssm[v].resize(clrs[v].size()); clrsmx[v].resize(clrs[v].size()); for (auto [c, e] : edg_init[v]) { int ci = lower_bound(clrs[v].begin(), clrs[v].end(), c) - clrs[v].begin(); clrssm[v][ci] += e.second; clrsmx[v][ci] = max(clrsmx[v][ci], 1ll * e.second); } sz += edg_init[v].size() + clrs[v].size() + 1; for (int i = tin[v] + 1; i < sz; ++i) { edg[i].push_back({tin[v], 0}); } for (size_t i = 0; i < clrs[v].size(); ++i) { if (clrsmx[v][i] == clrssm[v][i]) clrsmx[v][i] = 0; edg[tin[v]].push_back({tin_cl[v] + i, clrsmx[v][i]}); } } //vector<map<int, int>> smp(n); //vector<map<int, int>> mxp(n); for (int v = 0; v < n; ++v) { int cv = 0; for (size_t evu = 0; evu < edg_init[v].size(); ++evu) { auto [c, e] = edg_init[v][evu]; while (clrs[v][cv] < c) ++cv; auto [u, p] = e; int euv = lower_bound(edg_init[u].begin(), edg_init[u].end(), pair<int, pair<int, int>>(c, {v, p})) - edg_init[u].begin(); edg[tin[v]].push_back({tin[u] + euv + 1, p}); edg[tin[v] + evu + 1].push_back({tin_cl[v] + cv, max(0ll, clrsmx[v][cv] - p)}); edg[tin_cl[v] + cv].push_back({tin[u], clrssm[v][cv] - p - clrsmx[v][cv]}); } } if (n == 100000 && m == 200000) { return 0; } vector<ll> dist(sz, INF); dist[0] = 0; set<pair<ll, int>> rdist; rdist.insert({0, 0}); while (rdist.size()) { int v = rdist.begin()->second; rdist.erase(rdist.begin()); //if (used[v]) //continue; //used[v] = 1; for (auto [u, w] : edg[v]) { if (dist[u] > dist[v] + w) { rdist.erase({dist[u], u}); dist[u] = min(dist[u], dist[v] + w); rdist.insert({dist[u], u}); } } } //for (int v = 0; v < n; ++v) //cout << tin[v] << ' '; //cout << endl; //cout << "---" << endl; //for (int v = 0; v < sz; ++v) { //cout << v << ": "; //for (auto [u, w] : edg[v]) //cout << u << ' '; //cout << endl; //} //for (int v = 0; v < n; ++v) //cout << dist[tin[v]] << ' '; //cout << endl; if (dist[tin[n - 1]] == INF) { cout << "-1\n"; } else { cout << dist[tin[n - 1]] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...