제출 #882981

#제출 시각아이디문제언어결과실행 시간메모리
882981MilosMilutinovicWild Boar (JOI18_wild_boar)C++14
62 / 100
5062 ms998088 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m, t, l; cin >> n >> m >> t >> l; vector<vector<pair<int, int>>> g(n); for (int i = 0; i < m; i++) { int x, y, z; cin >> x >> y >> z; --x; --y; g[x].emplace_back(y, z); g[y].emplace_back(x, z); } vector<int> seq(l); for (int i = 0; i < l; i++) { cin >> seq[i]; --seq[i]; } vector<int> deg(n); for (int i = 0; i < n; i++) { deg[i] = (int) g[i].size(); } vector<vector<int>> idx(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < deg[i]; j++) { idx[i][g[i][j].first] = j; } } const long long inf = (long long) 1e18; vector<vector<vector<vector<long long>>>> dist(n, vector<vector<vector<long long>>>(n)); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (i == j) { continue; } dist[i][j].resize(deg[i]); for (int k = 0; k < deg[i]; k++) { dist[i][j][k] = vector<long long>(deg[j], inf); } } } vector<vector<long long>> d(n); for (int i = 0; i < n; i++) { d[i].resize(deg[i]); } vector<int> ia(n), ib(n); set<tuple<long long, int, int>> que; for (int ver = 0; ver < n; ver++) { for (int e = 0; e < deg[ver]; e++) { for (int i = 0; i < n; i++) { for (int j = 0; j < deg[i]; j++) { d[i][j] = inf; } ia[i] = -1; ib[i] = -1; } int to = g[ver][e].first; int w = g[ver][e].second; d[to][idx[to][ver]] = w; que.clear(); que.emplace(d[to][idx[to][ver]], to, idx[to][ver]); ia[to] = idx[to][ver]; auto Update = [&](int x, int y, long long z) { if (ia[x] == y || ib[x] == y) { que.erase(que.find({d[x][y], x, y})); } d[x][y] = z; if (ia[x] == y) { return; } if (ib[x] == y) { if (d[x][y] < d[x][ia[x]]) { swap(ia[x], ib[x]); } return; } if (ia[x] == -1) { ia[x] = y; que.emplace(d[x][y], x, y); return; } if (ib[x] == -1) { if (d[x][y] < d[x][ia[x]]) { swap(ia[x], ib[x]); ia[x] = y; } else { ib[x] = y; } que.emplace(d[x][y], x, y); return; } if (d[x][y] >= d[x][ia[x]] && d[x][y] < d[x][ib[x]]) { que.erase(que.find({d[x][ib[x]], x, ib[x]})); ib[x] = y; que.emplace(d[x][y], x, y); return; } if (d[x][y] < d[x][ia[x]]) { que.erase(que.find({d[x][ib[x]], x, ib[x]})); swap(ia[x], ib[x]); ia[x] = y; que.emplace(d[x][y], x, y); } }; while (!que.empty()) { auto it = que.begin(); int v = get<1>(*it); int lst = get<2>(*it); que.erase(it); for (int i = 0; i < deg[v]; i++) { if (i == lst) { continue; } int to = g[v][i].first; int w = g[v][i].second; if (d[to][idx[to][v]] > d[v][lst] + w) { Update(to, idx[to][v], d[v][lst] + w); assert((int) que.size() <= 2 * n); } } } for (int i = ver + 1; i < n; i++) { if (i == ver) { continue; } for (int j = 0; j < deg[i]; j++) { dist[ver][i][e][j] = d[i][j]; } } } } vector<vector<vector<vector<int>>>> good(n, vector<vector<vector<int>>>(n, vector<vector<int>>(2))); vector<vector<int>> cc(n, vector<int>(2)); for (int from = 0; from < n; from++) { for (int to = 0; to < n; to++) { if (from == to) { continue; } vector<pair<int, int>> order; for (int i = 0; i < deg[from]; i++) { for (int j = 0; j < deg[to]; j++) { order.emplace_back(i, j); } } if (from <= to) { sort(order.begin(), order.end(), [&](pair<int, int> a, pair<int, int> b) { return dist[from][to][a.first][a.second] < dist[from][to][b.first][b.second]; }); } else { sort(order.begin(), order.end(), [&](pair<int, int> a, pair<int, int> b) { return dist[to][from][a.second][a.first] < dist[to][from][b.second][b.first]; }); } int total = 0; for (auto& p : order) { if (cc[p.first][0] >= 2 || cc[p.second][1] >= 2) { continue; } good[from][to][0].push_back(p.first); good[from][to][1].push_back(p.second); cc[p.first][0] += 1; cc[p.second][1] += 1; total += 1; if (total >= 5) { break; } } for (int i = 0; i < deg[from]; i++) { cc[i][0] = 0; } for (int i = 0; i < deg[to]; i++) { cc[i][1] = 0; } } } vector<vector<int>> f(l); for (int i = 0; i < l; i++) { if (i > 0) { for (int j : good[seq[i - 1]][seq[i]][1]) { f[i].push_back(j); } } if (i + 1 < l) { for (int j : good[seq[i]][seq[i + 1]][0]) { f[i].push_back(j); } } sort(f[i].begin(), f[i].end()); f[i].erase(unique(f[i].begin(), f[i].end()), f[i].end()); } auto Update = [&](int i) { f[i].clear(); if (i > 0) { for (int j : good[seq[i - 1]][seq[i]][1]) { f[i].push_back(j); } } if (i + 1 < l) { for (int j : good[seq[i]][seq[i + 1]][0]) { f[i].push_back(j); } } sort(f[i].begin(), f[i].end()); f[i].erase(unique(f[i].begin(), f[i].end()), f[i].end()); }; vector<vector<vector<long long>>> st(4 * l); auto Pull = [&](int x, int l, int r) { int mid = l + r >> 1; st[x].clear(); for (int ll = 0; ll < (int) st[x * 2].size(); ll++) { for (int lr = 0; lr < (int) st[x * 2][ll].size(); lr++) { if (st[x].empty()) { st[x].resize((int) st[x * 2].size()); } for (int rl = 0; rl < (int) st[x * 2 + 1].size(); rl++) { if (st[x][ll].empty()) { st[x][ll] = vector<long long>((int) st[x * 2 + 1][rl].size(), inf); } if (lr == rl) { continue; } for (int rr = 0; rr < (int) st[x * 2 + 1][rl].size(); rr++) { st[x][ll][rr] = min(st[x][ll][rr], st[x * 2][ll][lr] + st[x * 2 + 1][rl][rr]); } } } } }; function<void(int, int, int)> Build = [&](int x, int l, int r) { if (l == r) { st[x].resize(f[l].size()); for (int i = 0; i < f[l].size(); i++) { st[x][i] = vector<long long>(f[l + 1].size(), inf); } for (int i = 0; i < f[l].size(); i++) { for (int j = 0; j < f[l + 1].size(); j++) { if (seq[l] <= seq[l + 1]) { st[x][i][j] = min(st[x][i][j], dist[seq[l]][seq[l + 1]][f[l][i]][f[l + 1][j]]); } else { st[x][i][j] = min(st[x][i][j], dist[seq[l + 1]][seq[l]][f[l + 1][j]][f[l][i]]); } } } return; } int mid = l + r >> 1; Build(x * 2, l, mid); Build(x * 2 + 1, mid + 1, r); Pull(x, l, r); }; function<void(int, int, int, int)> Modify = [&](int x, int l, int r, int p) { if (l == r) { st[x].clear(); st[x].resize(f[l].size()); for (int i = 0; i < f[l].size(); i++) { st[x][i] = vector<long long>(f[l + 1].size(), inf); } for (int i = 0; i < f[l].size(); i++) { for (int j = 0; j < f[l + 1].size(); j++) { if (seq[l] <= seq[l + 1]) { st[x][i][j] = min(st[x][i][j], dist[seq[l]][seq[l + 1]][f[l][i]][f[l + 1][j]]); } else { st[x][i][j] = min(st[x][i][j], dist[seq[l + 1]][seq[l]][f[l + 1][j]][f[l][i]]); } } } return; } int mid = l + r >> 1; if (p <= mid) { Modify(x * 2, l, mid, p); } else { Modify(x * 2 + 1, mid + 1, r, p); } Pull(x, l, r); }; for (int i = 0; i < l; i++) { Update(i); } Build(1, 0, l - 2); auto Solve = [&]() { long long res = inf; for (int i = 0; i < st[1].size(); i++) { for (int j = 0; j < st[1][i].size(); j++) { res = min(res, st[1][i][j]); } } return (res == inf ? -1LL : res); }; while (t--) { int p, x; cin >> p >> x; --p; --x; seq[p] = x; Update(p); if (p > 0) { Update(p - 1); } if (p <= l - 2) { Modify(1, 0, l - 2, p); } if (p + 1 <= l - 2) { Modify(1, 0, l - 2, p + 1); } if (p > 0) { Modify(1, 0, l - 2, p - 1); } if (p > 1) { Modify(1, 0, l - 2, p - 2); } cout << Solve() << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

wild_boar.cpp: In lambda function:
wild_boar.cpp:212:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  212 |     int mid = l + r >> 1;
      |               ~~^~~
wild_boar.cpp:212:9: warning: unused variable 'mid' [-Wunused-variable]
  212 |     int mid = l + r >> 1;
      |         ^~~
wild_boar.cpp: In lambda function:
wild_boar.cpp:236:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:239:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:240:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |         for (int j = 0; j < f[l + 1].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:250:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  250 |     int mid = l + r >> 1;
      |               ~~^~~
wild_boar.cpp: In lambda function:
wild_boar.cpp:259:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  259 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:262:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  262 |       for (int i = 0; i < f[l].size(); i++) {
      |                       ~~^~~~~~~~~~~~~
wild_boar.cpp:263:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  263 |         for (int j = 0; j < f[l + 1].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:273:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  273 |     int mid = l + r >> 1;
      |               ~~^~~
wild_boar.cpp: In lambda function:
wild_boar.cpp:287:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  287 |     for (int i = 0; i < st[1].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~
wild_boar.cpp:288:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  288 |       for (int j = 0; j < st[1][i].size(); j++) {
      |                       ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...