oj.uz

Submission #416908

# Submission time Handle Problem Language Result Execution time Memory
416908 2021-06-03T07:11:54 Z Mamnoon_Siam Wild Boar (JOI18_wild_boar) C++17
100 / 100
 10593 ms 712724 KB 
#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
#define fi first
#define se second
#define all(v) begin(v), end(v)
#define sz(v) (int)(v.size())
using pli = pair<ll, int>;
template<typename T>
inline void chkmin(T& x, T y) {
  x = x < y ? x : y;
}

const ll inf = 1e18;

tuple<ll,int,int> shortest_path(vector<pair<ii,ll>>& ls, int anot, int bnot) {
  // best path *---a--->--...-->---b---* in ls s.t. a != anot, b != bnot
  tuple<ll,int,int> opt{inf, -1, -1};
  for(auto [pa, w] : ls) {
    auto [s, t] = pa;
    if(s != anot and t != bnot) {
      opt = min(opt, make_tuple(w, s, t));
    }
  }
  return opt;
}

struct path {
  int s, t;
  ll w;
};

vector<path> get_top5(vector<pair<ii,ll>>& ls) {
  vector<path> ret;
  auto [w1, a1, b1] = shortest_path(ls, -1, -1);
  auto [w2, a2, b2] = shortest_path(ls, a1, -1);
  auto [w3, a3, b3] = shortest_path(ls, a1, b2);
  auto [w4, a4, b4] = shortest_path(ls, -1, b1);
  auto [w5, a5, b5] = shortest_path(ls, a4, b1);
  if(~a1) ret.push_back({a1, b1, w1});
  if(~a2) ret.push_back({a2, b2, w2});
  if(~a3) ret.push_back({a3, b3, w3});
  if(~a4) ret.push_back({a4, b4, w4});
  if(~a5) ret.push_back({a5, b5, w5});
  return ret;
}

vector<path> merge(vector<path> L, vector<path> R) {
  map<ii, ll> opt;
  for(path& l : L) {
    for(path& r : R) {
      if(l.t != r.s) {
        if(!opt.count(ii(l.s, r.t))) {
          opt[ii(l.s, r.t)] = l.w + r.w;
        } else {
          chkmin(opt[ii(l.s, r.t)], l.w + r.w);
        }
      }
    }
  }
  std::vector<path> ret;
  vector<pair<ii,ll>> ls(all(opt));
  return get_top5(ls);
}

int n, m, T, L;
int A[4004], B[4004], C[4004];
vi ine[2002], oute[2002];
ll cost[4004][4004]; // cost[i][j] = shortest path from i-th directed edge to j-th directed edge
int X[100005];
vector<path> top5[2002][2002];
vector<path> tree[100005 << 2];

void build(int u = 1, int b = 1, int e = L-1) {
  if(b == e) {
    tree[u] = top5[X[b]][X[b+1]];
    return;
  }
  int mid = (b + e) >> 1;
  build(u << 1, b, mid);
  build(u << 1 | 1, mid+1, e);
  tree[u] = merge(tree[u << 1], tree[u << 1 | 1]);
}

void update(int pos, int u = 1, int b = 1, int e = L-1) {
  if(b == e) {
    tree[u] = top5[X[b]][X[b+1]];
    return;
  }
  int mid = (b + e) >> 1;
  if(pos <= mid)
    update(pos, u << 1, b, mid);
  else
    update(pos, u << 1 | 1, mid+1, e);
  tree[u] = merge(tree[u << 1], tree[u << 1 | 1]);
}

#ifdef LOCAL
#include "../debug.h"
#else
#define debug(...)
#endif
int main(int argc, char const *argv[])
{
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d %d %d %d", &n, &m, &T, &L);
  for(int i = 1; i <= m; ++i) {
    scanf("%d %d %d", &A[2*i], &B[2*i], &C[2*i]);
    A[2*i+1] = B[2*i];
    B[2*i+1] = A[2*i];
    C[2*i+1] = C[2*i];
    ine[B[2*i]].emplace_back(2*i);
    oute[A[2*i]].emplace_back(2*i);
    ine[B[2*i+1]].emplace_back(2*i+1);
    oute[A[2*i+1]].emplace_back(2*i+1);
  }
  for(int i = 1; i <= n; ++i) {
    debug(ine[i], oute[i]);
  }
  for(int i = 1; i <= L; ++i) {
    scanf("%d", &X[i]);
  }
  for(int src = 2; src <= 2*m+1; ++src) {
  // for(int src : {4}) {
    vector<bool> done(2*m+2);
    ll *dis = cost[src];
    fill(dis+2, dis+2*m+2, inf);
    debug(vector<ll>(dis+2, dis+2*m+2));
    dis[src] = C[src];
    debug(dis[src]);
    priority_queue<pli, vector<pli>, greater<pli>> Q;
    Q.emplace(dis[src], src);
    while(sz(Q)) {
      int u = Q.top().se;
      debug(u);
      Q.pop();
      if(done[u]) continue;
      done[u] = 1;
      for(int v : oute[B[u]]) if((u^v)>>1) {
        debug(v);
        ll nw = dis[u] + C[v];
        debug(nw);
        debug(dis[7]);
        if(nw < dis[v]) {
          dis[v] = nw;
          Q.emplace(dis[v], v);
        }
      }
    }
    debug(dis[7]);
  }
  for(int a = 1; a <= n; ++a) {
    for(int b = 1; b <= n; ++b) if(a != b) {
      vector<pair<ii,ll>> ls;
      for(int s : oute[a])
        for(int t : ine[b])
          if(cost[s][t] < inf)
            ls.push_back({{s>>1, t>>1}, cost[s][t]});
      top5[a][b] = get_top5(ls);
    }
  }
  build();
  while(T--) {
    int p, q;
    scanf("%d %d", &p, &q);
    X[p] = q;

    update(p-1);
    update(p);

    ll ans = inf;
    for(path& pa : tree[1]) chkmin(ans, pa.w);
    printf("%lld\n", ans == inf ? -1 : ans);
  }
  return 0;
}

Compilation message

wild_boar.cpp: In function 'int main(int, const char**)':
wild_boar.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d %d %d %d", &n, &m, &T, &L);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d %d %d", &A[2*i], &B[2*i], &C[2*i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:126:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     scanf("%d", &X[i]);
      |     ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     scanf("%d %d", &p, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 103876 KB Output is correct
2 Correct 69 ms 103976 KB Output is correct
3 Correct 68 ms 103920 KB Output is correct
4 Correct 69 ms 103876 KB Output is correct
5 Correct 68 ms 103876 KB Output is correct
6 Correct 69 ms 103868 KB Output is correct
7 Correct 68 ms 104044 KB Output is correct
8 Correct 69 ms 104000 KB Output is correct
9 Correct 68 ms 103984 KB Output is correct
10 Correct 68 ms 103996 KB Output is correct
11 Correct 71 ms 104000 KB Output is correct
12 Correct 69 ms 103876 KB Output is correct
13 Correct 70 ms 103876 KB Output is correct
14 Correct 68 ms 104004 KB Output is correct
15 Correct 69 ms 103876 KB Output is correct
16 Correct 69 ms 103876 KB Output is correct
17 Correct 68 ms 103876 KB Output is correct
18 Correct 68 ms 103972 KB Output is correct
19 Correct 70 ms 104000 KB Output is correct
20 Correct 70 ms 103996 KB Output is correct
21 Correct 69 ms 103988 KB Output is correct
22 Correct 71 ms 103920 KB Output is correct
23 Correct 70 ms 103976 KB Output is correct
24 Correct 71 ms 104112 KB Output is correct
25 Correct 68 ms 103920 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 103876 KB Output is correct
2 Correct 69 ms 103976 KB Output is correct
3 Correct 68 ms 103920 KB Output is correct
4 Correct 69 ms 103876 KB Output is correct
5 Correct 68 ms 103876 KB Output is correct
6 Correct 69 ms 103868 KB Output is correct
7 Correct 68 ms 104044 KB Output is correct
8 Correct 69 ms 104000 KB Output is correct
9 Correct 68 ms 103984 KB Output is correct
10 Correct 68 ms 103996 KB Output is correct
11 Correct 71 ms 104000 KB Output is correct
12 Correct 69 ms 103876 KB Output is correct
13 Correct 70 ms 103876 KB Output is correct
14 Correct 68 ms 104004 KB Output is correct
15 Correct 69 ms 103876 KB Output is correct
16 Correct 69 ms 103876 KB Output is correct
17 Correct 68 ms 103876 KB Output is correct
18 Correct 68 ms 103972 KB Output is correct
19 Correct 70 ms 104000 KB Output is correct
20 Correct 70 ms 103996 KB Output is correct
21 Correct 69 ms 103988 KB Output is correct
22 Correct 71 ms 103920 KB Output is correct
23 Correct 70 ms 103976 KB Output is correct
24 Correct 71 ms 104112 KB Output is correct
25 Correct 68 ms 103920 KB Output is correct
26 Correct 73 ms 104364 KB Output is correct
27 Correct 105 ms 109944 KB Output is correct
28 Correct 102 ms 109448 KB Output is correct
29 Correct 373 ms 134460 KB Output is correct
30 Correct 379 ms 134360 KB Output is correct
31 Correct 368 ms 134432 KB Output is correct
32 Correct 342 ms 134388 KB Output is correct
33 Correct 358 ms 136300 KB Output is correct
34 Correct 351 ms 136168 KB Output is correct
35 Correct 332 ms 136152 KB Output is correct
36 Correct 339 ms 136132 KB Output is correct
37 Correct 355 ms 136120 KB Output is correct
38 Correct 361 ms 138632 KB Output is correct
39 Correct 367 ms 138744 KB Output is correct
40 Correct 353 ms 138688 KB Output is correct
41 Correct 344 ms 138636 KB Output is correct
42 Correct 309 ms 140560 KB Output is correct
43 Correct 329 ms 141772 KB Output is correct
44 Correct 333 ms 141896 KB Output is correct
45 Correct 209 ms 130608 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 103876 KB Output is correct
2 Correct 69 ms 103976 KB Output is correct
3 Correct 68 ms 103920 KB Output is correct
4 Correct 69 ms 103876 KB Output is correct
5 Correct 68 ms 103876 KB Output is correct
6 Correct 69 ms 103868 KB Output is correct
7 Correct 68 ms 104044 KB Output is correct
8 Correct 69 ms 104000 KB Output is correct
9 Correct 68 ms 103984 KB Output is correct
10 Correct 68 ms 103996 KB Output is correct
11 Correct 71 ms 104000 KB Output is correct
12 Correct 69 ms 103876 KB Output is correct
13 Correct 70 ms 103876 KB Output is correct
14 Correct 68 ms 104004 KB Output is correct
15 Correct 69 ms 103876 KB Output is correct
16 Correct 69 ms 103876 KB Output is correct
17 Correct 68 ms 103876 KB Output is correct
18 Correct 68 ms 103972 KB Output is correct
19 Correct 70 ms 104000 KB Output is correct
20 Correct 70 ms 103996 KB Output is correct
21 Correct 69 ms 103988 KB Output is correct
22 Correct 71 ms 103920 KB Output is correct
23 Correct 70 ms 103976 KB Output is correct
24 Correct 71 ms 104112 KB Output is correct
25 Correct 68 ms 103920 KB Output is correct
26 Correct 73 ms 104364 KB Output is correct
27 Correct 105 ms 109944 KB Output is correct
28 Correct 102 ms 109448 KB Output is correct
29 Correct 373 ms 134460 KB Output is correct
30 Correct 379 ms 134360 KB Output is correct
31 Correct 368 ms 134432 KB Output is correct
32 Correct 342 ms 134388 KB Output is correct
33 Correct 358 ms 136300 KB Output is correct
34 Correct 351 ms 136168 KB Output is correct
35 Correct 332 ms 136152 KB Output is correct
36 Correct 339 ms 136132 KB Output is correct
37 Correct 355 ms 136120 KB Output is correct
38 Correct 361 ms 138632 KB Output is correct
39 Correct 367 ms 138744 KB Output is correct
40 Correct 353 ms 138688 KB Output is correct
41 Correct 344 ms 138636 KB Output is correct
42 Correct 309 ms 140560 KB Output is correct
43 Correct 329 ms 141772 KB Output is correct
44 Correct 333 ms 141896 KB Output is correct
45 Correct 209 ms 130608 KB Output is correct
46 Correct 286 ms 121404 KB Output is correct
47 Correct 6408 ms 288268 KB Output is correct
48 Correct 5787 ms 335532 KB Output is correct
49 Correct 4974 ms 394356 KB Output is correct
50 Correct 5188 ms 394004 KB Output is correct
51 Correct 5689 ms 394132 KB Output is correct
52 Correct 3897 ms 394040 KB Output is correct
53 Correct 3854 ms 393980 KB Output is correct
54 Correct 3910 ms 394080 KB Output is correct
55 Correct 4070 ms 393952 KB Output is correct
56 Correct 3960 ms 423556 KB Output is correct
57 Correct 3963 ms 456220 KB Output is correct
58 Correct 3982 ms 491324 KB Output is correct
59 Correct 3961 ms 529412 KB Output is correct
60 Correct 3974 ms 570096 KB Output is correct
61 Correct 3930 ms 613720 KB Output is correct
62 Correct 3950 ms 660224 KB Output is correct
63 Correct 3849 ms 709480 KB Output is correct
64 Correct 1742 ms 556804 KB Output is correct
65 Correct 1768 ms 556904 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 103876 KB Output is correct
2 Correct 69 ms 103976 KB Output is correct
3 Correct 68 ms 103920 KB Output is correct
4 Correct 69 ms 103876 KB Output is correct
5 Correct 68 ms 103876 KB Output is correct
6 Correct 69 ms 103868 KB Output is correct
7 Correct 68 ms 104044 KB Output is correct
8 Correct 69 ms 104000 KB Output is correct
9 Correct 68 ms 103984 KB Output is correct
10 Correct 68 ms 103996 KB Output is correct
11 Correct 71 ms 104000 KB Output is correct
12 Correct 69 ms 103876 KB Output is correct
13 Correct 70 ms 103876 KB Output is correct
14 Correct 68 ms 104004 KB Output is correct
15 Correct 69 ms 103876 KB Output is correct
16 Correct 69 ms 103876 KB Output is correct
17 Correct 68 ms 103876 KB Output is correct
18 Correct 68 ms 103972 KB Output is correct
19 Correct 70 ms 104000 KB Output is correct
20 Correct 70 ms 103996 KB Output is correct
21 Correct 69 ms 103988 KB Output is correct
22 Correct 71 ms 103920 KB Output is correct
23 Correct 70 ms 103976 KB Output is correct
24 Correct 71 ms 104112 KB Output is correct
25 Correct 68 ms 103920 KB Output is correct
26 Correct 73 ms 104364 KB Output is correct
27 Correct 105 ms 109944 KB Output is correct
28 Correct 102 ms 109448 KB Output is correct
29 Correct 373 ms 134460 KB Output is correct
30 Correct 379 ms 134360 KB Output is correct
31 Correct 368 ms 134432 KB Output is correct
32 Correct 342 ms 134388 KB Output is correct
33 Correct 358 ms 136300 KB Output is correct
34 Correct 351 ms 136168 KB Output is correct
35 Correct 332 ms 136152 KB Output is correct
36 Correct 339 ms 136132 KB Output is correct
37 Correct 355 ms 136120 KB Output is correct
38 Correct 361 ms 138632 KB Output is correct
39 Correct 367 ms 138744 KB Output is correct
40 Correct 353 ms 138688 KB Output is correct
41 Correct 344 ms 138636 KB Output is correct
42 Correct 309 ms 140560 KB Output is correct
43 Correct 329 ms 141772 KB Output is correct
44 Correct 333 ms 141896 KB Output is correct
45 Correct 209 ms 130608 KB Output is correct
46 Correct 286 ms 121404 KB Output is correct
47 Correct 6408 ms 288268 KB Output is correct
48 Correct 5787 ms 335532 KB Output is correct
49 Correct 4974 ms 394356 KB Output is correct
50 Correct 5188 ms 394004 KB Output is correct
51 Correct 5689 ms 394132 KB Output is correct
52 Correct 3897 ms 394040 KB Output is correct
53 Correct 3854 ms 393980 KB Output is correct
54 Correct 3910 ms 394080 KB Output is correct
55 Correct 4070 ms 393952 KB Output is correct
56 Correct 3960 ms 423556 KB Output is correct
57 Correct 3963 ms 456220 KB Output is correct
58 Correct 3982 ms 491324 KB Output is correct
59 Correct 3961 ms 529412 KB Output is correct
60 Correct 3974 ms 570096 KB Output is correct
61 Correct 3930 ms 613720 KB Output is correct
62 Correct 3950 ms 660224 KB Output is correct
63 Correct 3849 ms 709480 KB Output is correct
64 Correct 1742 ms 556804 KB Output is correct
65 Correct 1768 ms 556904 KB Output is correct
66 Correct 271 ms 128116 KB Output is correct
67 Correct 535 ms 176196 KB Output is correct
68 Correct 1195 ms 357724 KB Output is correct
69 Correct 1429 ms 359908 KB Output is correct
70 Correct 1664 ms 363944 KB Output is correct
71 Correct 10395 ms 290780 KB Output is correct
72 Correct 9965 ms 345800 KB Output is correct
73 Correct 7653 ms 397104 KB Output is correct
74 Correct 7625 ms 396944 KB Output is correct
75 Correct 7664 ms 397308 KB Output is correct
76 Correct 8942 ms 396512 KB Output is correct
77 Correct 9580 ms 396452 KB Output is correct
78 Correct 10593 ms 396416 KB Output is correct
79 Correct 7752 ms 458968 KB Output is correct
80 Correct 7694 ms 494256 KB Output is correct
81 Correct 8509 ms 531892 KB Output is correct
82 Correct 7357 ms 573340 KB Output is correct
83 Correct 8106 ms 616240 KB Output is correct
84 Correct 6989 ms 712724 KB Output is correct
85 Correct 4200 ms 560240 KB Output is correct