제출 #724728

#제출 시각아이디문제언어결과실행 시간메모리
724728GusterGoose27Wild Boar (JOI18_wild_boar)C++17
12 / 100
136 ms36768 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, bool> plb; typedef pair<ll, int> pli; const int MAXN = 2000; const int MAXM = 12000; const int MAX_PATH = 1e5; const ll inf = 1e15; class path { public: ll len; int s, e; path(ll l, int s, int e) : len(l), s(s), e(e) {} path() {} }; vector<int> edges[MAXN]; pii init_edge[2*MAXN]; // dest, weight vector<int> dual[MAXM]; int ecount = 0; int make_edge() { return (ecount++); } path dist[MAXN][MAXN][5]; // 0 : normal, 1 : first diff, 2 : f/e, 3 : e, 4 : e/f ll edge_dist[2*MAXN][2*MAXN]; bool vis[MAXM]; // bitset? int seq[MAX_PATH]; int n, m, t, l; path min(path a, path b) { if (a.len <= b.len) return a; return b; } path comb(path a, path b) { assert(a.e != b.s); if (a.len == inf || b.len == inf) return path(inf, -1, -2); return path(a.len+b.len, a.s, b.e); } class stree { public: int lp, rp; stree *l = nullptr; stree *r = nullptr; path seg[5]; stree(int lv, int rv) { lp = lv; rp = rv; if (lp < rp) { int mid = (lp+rp)/2; l = new stree(lp, mid); r = new stree(mid+1, rp); } make(); } int rdiff(int a) { if (a == 0) return 3; return 2; } void avoid(path seg[], int s, int e, int &a) { // best path avoiding these things if (seg[a].s == s) a = 1; if (seg[a].e == e) a = rdiff(a); if (seg[a].s == s) a++; } void make() { // really slow. Could probably be faster if (lp == rp) { for (int i = 0; i < 5; i++) seg[i] = dist[seq[lp]][seq[lp+1]][i]; return; } for (int i = 0; i < 5; i++) { int a = 0, b = 0; int lv = -2, rv = -2; if (i == 1 || i == 2) lv = seg[0].s; if (i == 4) lv = seg[3].s; if (i == 2) rv = seg[1].e; if (i == 3 || i == 4) rv = seg[0].e; avoid(l->seg, lv, -2, a); avoid(r->seg, l->seg[a].e, rv, b); seg[i] = comb(l->seg[a], r->seg[b]); a = 0, b = 0; avoid(r->seg, -2, rv, b); avoid(l->seg, lv, r->seg[b].s, a); seg[i] = min(seg[i], comb(l->seg[a], r->seg[b])); } } void upd(int p) { if (lp > p || rp < p) return; if (lp == rp) return make(); l->upd(p); r->upd(p); make(); } }; stree *tree; void dijkstra(int s) { fill(edge_dist[s], edge_dist[s]+2*m, inf); fill(vis, vis+MAXM, 0); // could optimize by expanding dists to make pq smaller priority_queue<pli, vector<pli>, greater<pli>> pq; pq.push(pli(init_edge[s].second, s)); while (!pq.empty()) { pli tp = pq.top(); pq.pop(); if (vis[tp.second]) continue; if (tp.second < 2*m) edge_dist[s][tp.second] = tp.first; vis[tp.second] = 1; for (int nxt: dual[tp.second]) { if (vis[nxt]) continue; ll ndist = tp.first+((nxt<2*m) ? init_edge[nxt].second : 0); pq.push(pli(ndist, nxt)); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> t >> l; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; init_edge[2*i] = pii(b, c); init_edge[2*i+1] = pii(a, c); edges[a].push_back(make_edge()); edges[b].push_back(make_edge()); } for (int i = 0; i < n; i++) { vector<int> pref; vector<int> suf; for (int j = 0; j < edges[i].size(); j++) { pref.push_back(make_edge()); dual[pref.back()].push_back(edges[i][j]); } for (int j = 0; j < edges[i].size(); j++) { suf.push_back(make_edge()); dual[suf.back()].push_back(edges[i][j]); } for (int j = 1; j < edges[i].size(); j++) { dual[pref[j]].push_back(pref[j-1]); dual[suf[j-1]].push_back(suf[j]); } for (int j = 0; j < edges[i].size(); j++) { if (j)dual[edges[i][j]^1].push_back(pref[j-1]); if (j<edges[i].size()-1)dual[edges[i][j]^1].push_back(suf[j+1]); } } for (int i = 0; i < 2*m; i++) dijkstra(i); // much cleaner? for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j][0] = path(inf, -1, -2); for (int a: edges[i]) { for (int b: edges[j]) { dist[i][j][0] = min(dist[i][j][0], path(edge_dist[a][b^1], a, b)); } } // 1 dist[i][j][1] = path(inf, -1, -2); for (int a: edges[i]) { if (a == dist[i][j][0].s) continue; for (int b: edges[j]) { dist[i][j][1] = min(dist[i][j][1], path(edge_dist[a][b^1], a, b)); } } // 2 dist[i][j][2] = path(inf, -1, -2); for (int a: edges[i]) { if (a == dist[i][j][0].s) continue; for (int b: edges[j]) { if (b == dist[i][j][1].e) continue; dist[i][j][2] = min(dist[i][j][2], path(edge_dist[a][b^1], a, b)); } } // 3 dist[i][j][3] = path(inf, -1, -2); for (int a: edges[i]) { for (int b: edges[j]) { if (b == dist[i][j][0].e) continue; dist[i][j][3] = min(dist[i][j][3], path(edge_dist[a][b^1], a, b)); } } // 4 dist[i][j][4] = path(inf, -1, -2); for (int a: edges[i]) { if (a == dist[i][j][3].s) continue; for (int b: edges[j]) { if (b == dist[i][j][0].e) continue; dist[i][j][4] = min(dist[i][j][4], path(edge_dist[a][b^1], a, b)); } } } } for (int i = 0; i < l; i++) { cin >> seq[i]; seq[i]--; } tree = new stree(0, l-2); for (int i = 0; i < t; i++) { int x, v; cin >> x >> v; x--; v--; seq[x] = v; if (x) tree->upd(x-1); if (x < l-1) tree->upd(x); if (tree->seg[0].len == inf) cout << "-1\n"; else cout << tree->seg[0].len << "\n"; } return 0; }

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

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:138:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   for (int j = 0; j < edges[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for (int j = 0; j < edges[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for (int j = 1; j < edges[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:150:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |   for (int j = 0; j < edges[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
wild_boar.cpp:152:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    if (j<edges[i].size()-1)dual[edges[i][j]^1].push_back(suf[j+1]);
      |        ~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...