제출 #767203

#제출 시각아이디문제언어결과실행 시간메모리
767203qwerasdfzxclWild Boar (JOI18_wild_boar)C++17
100 / 100
4494 ms231068 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; constexpr ll INF = 4e18; vector<pair<int, int>> adj0[6060]; pair<int, int> Edge[2020]; ll dist0[4040][4040], res0[4040]; int visited0[6060], F[2020]; ll (*dist)[4040]; vector<int> in[2020], out[2020]; int X[100100]; ll dp[100100][4]; struct Node{ ll W[4][4]; int S[4], E[4]; Node(){} ll ans(){ ll ret = INF; for (int i=0;i<4;i++){ for (int j=0;j<4;j++){ ret = min(ret, W[i][j]); } } return ret==INF?-1:ret; } Node operator + (const Node &N) const{ Node ret; for (int i=0;i<4;i++){ ret.S[i] = S[i]; ret.E[i] = N.E[i]; for (int j=0;j<4;j++){ ret.W[i][j] = INF; for (int k1=0;k1<4;k1++){ for (int k2=0;k2<4;k2++) if (abs(E[k1])!=abs(N.S[k2])){ ret.W[i][j] = min(ret.W[i][j], W[i][k1] + N.W[k2][j]); } } } } return ret; } }; Node initW(int p); struct Seg{ Node tree[400400]; void init(int i, int l, int r){ if (l==r){ tree[i] = initW(l); return; } int m = (l+r)>>1; init(i<<1, l, m); init(i<<1|1, m+1, r); tree[i] = tree[i<<1] + tree[i<<1|1]; } void update(int i, int l, int r, int p){ if (r<p || p<l) return; if (l==r){ tree[i] = initW(l); return; } int m = (l+r)>>1; update(i<<1, l, m, p); update(i<<1|1, m+1, r, p); tree[i] = tree[i<<1] + tree[i<<1|1]; } }tree; void dijkstra(int m, int s, ll (*dist)[4040], ll *res, vector<pair<int, int>> *adj){ int *visited = visited0 + 2020; fill(res-2020, res+2020, INF); fill(visited-2020, visited+4040, -1); priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq; vector<array<ll, 3>> st; res[s] = F[abs(s)]; pq.push({F[abs(s)], s, 0}); // printf("dijkstra from %d:\n", s); while(!pq.empty() || !st.empty()){ array<ll, 3> tmp; if (!st.empty()) {tmp = st.back(); st.pop_back();} else {tmp = pq.top(); pq.pop();} auto [dist, cur, p] = tmp; if (visited[cur]==-2) continue; if (visited[cur]==-1){ if (cur <= m){ // printf(" dist[%lld] = %lld\n", cur, res[cur]); visited[cur] = -2; for (auto &[v, w]:adj[cur]) if (visited[v]!=-2){ st.push_back({dist, v, cur}); } } else{ visited[cur] = abs(p); for (auto &[v, w]:adj[cur]) if (visited[v]!=-2 && abs(v)!=abs(p)){ res[v] = dist + w; pq.push({res[v], v, cur}); } } } else{ for (auto &[v, w]:adj[cur]) if (abs(v)==visited[cur] && visited[v]!=-2){ res[v] = dist + w; pq.push({res[v], v, cur}); } visited[cur] = -2; } } } map<int, Node> mp[2020]; Node initW(int p){ vector<ll> W; vector<int> S, E; if (mp[X[p]].find(X[p+1])!=mp[X[p]].end()){ return mp[X[p]][X[p+1]]; } W.push_back(INF); S.push_back(-1); E.push_back(-1); for (auto &s1:out[X[p]]){ for (auto &e1:in[X[p+1]]){ if (W.back() > dist[s1][e1]){ W.back() = dist[s1][e1]; S.back() = s1; E.back() = e1; } } } W.push_back(INF); S.push_back(-1); E.push_back(-1); for (auto &s2:out[X[p]]) if (s2!=S[0]){ for (auto &e2:in[X[p+1]]) if (e2!=E[0]){ if (W.back() > dist[s2][e2]){ W.back() = dist[s2][e2]; S.back() = s2; E.back() = e2; } } } W.push_back(INF); S.push_back(-1); E.push_back(-1); for (auto &s3:out[X[p]]) if (s3!=S[0]){ for (auto &e3:in[X[p+1]]) if (e3!=E[1]){ if (W.back() > dist[s3][e3]){ W.back() = dist[s3][e3]; S.back() = s3; E.back() = e3; } } } W.push_back(INF); S.push_back(-1); E.push_back(-1); for (auto &s4:out[X[p]]) if (s4!=S[1]){ for (auto &e4:in[X[p+1]]) if (e4!=E[0]){ if (W.back() > dist[s4][e4]){ W.back() = dist[s4][e4]; S.back() = s4; E.back() = e4; } } } Node ret; for (int i=0;i<4;i++){ for (int j=0;j<4;j++){ if (i!=j) ret.W[i][j] = INF; else ret.W[i][j] = W[i]; } ret.S[i] = S[i]; ret.E[i] = E[i]; } mp[X[p]][X[p+1]] = ret; return ret; // printf("init %d to %d -> ", X[p], X[p+1]); // for (int i=0;i<4;i++){ // printf("(%lld / %d, %d) ", W[p][i], S[p][i], E[p][i]); // } // printf("\n"); } int main(){ int n, m, q, l; scanf("%d %d %d %d", &n, &m, &q, &l); vector<pair<int, int>> *adj = adj0 + m; for (int i=1;i<=m;i++){ int x, y, z; scanf("%d %d %d", &x, &y, &z); Edge[i] = {x, y}; F[i] = z; adj[i].emplace_back(y+m, 0); adj[-i].emplace_back(x+m, 0); adj[x+m].emplace_back(i, z); adj[y+m].emplace_back(-i, z); out[x].push_back(i); out[y].push_back(-i); in[x].push_back(-i); in[y].push_back(i); } dist = (ll (*)[4040])(&(dist0[2020][2020])); ll *res = res0 + 2020; for (int i=1;i<=m;i++){ dijkstra(m, i, dist, res, adj); for (int j=-m;j<=m;j++) dist[i][j] = res[j]; dijkstra(m, -i, dist, res, adj); for (int j=-m;j<=m;j++) dist[-i][j] = res[j]; } for (int i=1;i<=l;i++) scanf("%d", X+i); tree.init(1, 1, l-1); while(q--){ int pp, qq; scanf("%d %d", &pp, &qq); X[pp] = qq; if (pp > 1) tree.update(1, 1, l-1, pp-1); if (pp < l) tree.update(1, 1, l-1, pp); printf("%lld\n", tree.tree[1].ans()); } // int pp, qq; // scanf("%d %d", &pp, &qq); // X[pp] = qq; // for (int i=1;i<l;i++){ // initW(i, dist); // for (int j=0;j<4;j++){ // dp[i+1][j] = INF; // if (i==1) {dp[i+1][j] = W[1][j]; continue;} // if (W[i][j]==INF) continue; // for (int k=0;k<4;k++) if (abs(E[i-1][k])!=abs(S[i][j])){ // dp[i+1][j] = min(dp[i+1][j], dp[i][k] + W[i][j]); // } // } // } // ll rans = *min_element(dp[l], dp[l]+4); // if (rans==INF) rans = -1; // printf("%lld\n", rans); }

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

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:219:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |  scanf("%d %d %d %d", &n, &m, &q, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:224:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |   scanf("%d %d %d", &x, &y, &z);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:251:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  251 |  for (int i=1;i<=l;i++) scanf("%d", X+i);
      |                         ~~~~~^~~~~~~~~~~
wild_boar.cpp:256:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  256 |   scanf("%d %d", &pp, &qq);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...