oj.uz

Submission #893070

# Submission time Handle Problem Language Result Execution time Memory
893070 2023-12-26T13:11:22 Z guechotjrhh Wild Boar (JOI18_wild_boar) C++14
100 / 100
 5376 ms 826324 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long int;
using pl = tuple<ll, ll>;
using tl = tuple<ll, ll, ll>;

const ll INFLL = 1e18;

ll N, M, T, L;
vector<tl> G[2010]; // (to, cost, id)

vector<tl> edges; // (from, to, cost)

vector<ll> eds[4010];

ll x[200010];
ll p[200010];
ll q[200010];

vector<tl> sp[2010][2010]; // (cost, next_start, prev_end)
vector<tl> node[400010]; // (cost, next_start, prev_end)

ll size = 1;

vector<tl> calc_top_five(vector<tl> ps){
  vector<tl> res(5, make_tuple(INFLL, INFLL, INFLL));
  int n = ps.size();
  for(int i = 0; i < n; i++){
    if(get<0>(ps[i]) < get<0>(res[0])){
      res[0] = ps[i];
    }
  }
  for(int i = 0; i < n; i++){
    if(get<1>(ps[i]) != get<1>(res[0]) && get<0>(ps[i])< get<0>(res[1])){
      res[1] = ps[i];
    }
    if(get<2>(ps[i]) != get<2>(res[0]) && get<0>(ps[i])< get<0>(res[3])){
      res[3] = ps[i];
    }
  }
  for(int i = 0; i < n; i++){
    if(get<1>(ps[i]) != get<1>(res[0]) && get<2>(ps[i]) != get<2>(res[1]) && get<0>(ps[i]) < get<0>(res[2])){
      res[2] = ps[i];
    }
    if(get<2>(ps[i]) != get<2>(res[0]) && get<1>(ps[i]) != get<1>(res[3]) && get<0>(ps[i]) < get<0>(res[4])){
      res[4] = ps[i];
    }
  }
  return res;
}

vector<tl> merge(vector<tl> s, vector<tl> t){
  vector<tl> ps(0);
  for(int i = 0; i < (int)s.size(); i++){
    for(int j = 0; j < (int)t.size(); j++){
      if(get<2>(s[i]) != get<1>(t[j])){
        ps.emplace_back(get<0>(s[i]) + get<0>(t[j]), get<1>(s[i]), get<2>(t[j]));
      }
    }
  }
  return calc_top_five(ps);
}

void init_segment_tree(ll k, ll l, ll r){
  if(r - l == 1){
    if(l < L-1){
      node[k] = sp[x[l]][x[l+1]];
    } else {
      node[k] = vector<tl>(5, make_tuple(INFLL, INFLL, INFLL));
    }
  } else {
    init_segment_tree(k*2+1, l, (l+r)/2);
    init_segment_tree(k*2+2, (l+r)/2, r);
    node[k] = merge(node[k*2+1], node[k*2+2]);
  }
}

void init_segment_tree(){
  size = 1;
  while(size < L-1){
    size *= 2;
  }
  init_segment_tree(0, 0, size);
}

void update(ll p, ll k, ll l, ll r){
  if(r - l == 1){
    assert(l == p && l < L-1);
    node[k] = sp[x[l]][x[l+1]];
  } else {
    ll m = (l + r) / 2;
    if(p < m){
      update(p, k*2+1, l, m);
    } else {
      update(p, k*2+2, m, r);
    }
    node[k] = merge(node[k*2+1], node[k*2+2]);
  }
}

void update(ll p){
  update(p, 0, 0, size);
}

vector<tl> query(ll k, ll l, ll r){
  if(r <= L-1){
    return node[k];
  } else if(L-1 <= l){
    assert(false);
  } else {
    ll m = (l+r)/2;
    vector<tl> resa = query(k*2+1, l, m);
    if(L-1 <= m){
      return resa;
    }
    vector<tl> resb = query(k*2+2, m, r);
    return merge(resa, resb);
  }
}

ll answer(){
  return get<0>(query(0, 0, size)[0]);
}

vector<ll> dijkstra(ll s){
  vector<ll> dist(2*M, INFLL);
  dist[s] = get<2>(edges[s]);
  vector<ll> state(N, -1);
  priority_queue<pl, vector<pl>, greater<pl> > que;
  que.emplace(get<2>(edges[s]), s);
  while(!que.empty()){
    ll d, p;
    tie(d, p) = que.top();
    que.pop();
    if(d > dist[p]){
      continue;
    }
    ll cur = get<1>(edges[p]);
    if(state[cur] == -1){
      for(auto &w: G[cur]){
        ll to, co, id;
        tie(to, co, id) = w;
        if(id/2 == p/2){
          continue;
        }
        if(d + co < dist[id]){
          dist[id] = d + co;
          que.emplace(dist[id], id);
        }
      }
      state[cur] = p;
    } else if(p != state[cur]){
      ll id = (state[cur]/2*2) + (1 - state[cur]%2);
      ll co = get<2>(edges[id]);
      if(d + co < dist[id]){
        dist[id] = d + co;
        que.emplace(dist[id], id);
      }
   } 
 } 
  return dist;
}

void input(){
  scanf("%lld %lld %lld %lld", &N, &M, &T, &L);
  for(ll i = 0; i < M; i++){
    ll a, b, c;
    scanf("%lld %lld %lld", &a, &b, &c);
    a--;
    b--;
    G[a].emplace_back(b, c, 2*i);
    G[b].emplace_back(a, c, 2*i+1);
    edges.emplace_back(a, b, c);
    edges.emplace_back(b, a, c);
  }
  for(ll i = 0; i < L; i++){
    scanf("%lld", &x[i]);
    x[i]--;
  }
  for(ll i = 0; i < T; i++){
    scanf("%lld %lld", &p[i], &q[i]);
    p[i]--;
    q[i]--;
  }
}

int main(){
  input();

  for(int i = 0; i < 2*M; i++){
    eds[i] = dijkstra(i);
  }
  
  for(int i = 0; i < 2*M; i++){
    for(int j = 0; j < 2*M; j++){
      ll s, t, a, b, _;
      tie(s, a, _) = edges[i];
      tie(b, t, _) = edges[j];
      sp[s][t].emplace_back(eds[i][j], a, b);
    }
  }

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      sp[i][j] = calc_top_five(sp[i][j]);
    }
  }

  init_segment_tree();
  
  for(ll i = 0; i < T; i++){
    x[p[i]] = q[i];
    if(p[i] < L-1){
      update(p[i]);
    }
    if(p[i] > 0){
      update(p[i]-1);
    }
    ll ans = answer();
    if(ans == INFLL){
      ans = -1;
    }
    printf("%lld\n", ans);
  }

  return 0;
}

Compilation message

wild_boar.cpp: In function 'void input()':
wild_boar.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |   scanf("%lld %lld %lld %lld", &N, &M, &T, &L);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |     scanf("%lld %lld %lld", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |     scanf("%lld", &x[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
wild_boar.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |     scanf("%lld %lld", &p[i], &q[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 109392 KB Output is correct
2 Correct 25 ms 109464 KB Output is correct
3 Correct 23 ms 109544 KB Output is correct
4 Correct 23 ms 109300 KB Output is correct
5 Correct 23 ms 109404 KB Output is correct
6 Correct 23 ms 109392 KB Output is correct
7 Correct 23 ms 109504 KB Output is correct
8 Correct 23 ms 109404 KB Output is correct
9 Correct 23 ms 109540 KB Output is correct
10 Correct 24 ms 109504 KB Output is correct
11 Correct 23 ms 109404 KB Output is correct
12 Correct 24 ms 109392 KB Output is correct
13 Correct 24 ms 109404 KB Output is correct
14 Correct 23 ms 109404 KB Output is correct
15 Correct 23 ms 109404 KB Output is correct
16 Correct 23 ms 109400 KB Output is correct
17 Correct 23 ms 109404 KB Output is correct
18 Correct 23 ms 109404 KB Output is correct
19 Correct 24 ms 109400 KB Output is correct
20 Correct 23 ms 109404 KB Output is correct
21 Correct 23 ms 109456 KB Output is correct
22 Correct 23 ms 109768 KB Output is correct
23 Correct 24 ms 109520 KB Output is correct
24 Correct 23 ms 109404 KB Output is correct
25 Correct 24 ms 109292 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 109392 KB Output is correct
2 Correct 25 ms 109464 KB Output is correct
3 Correct 23 ms 109544 KB Output is correct
4 Correct 23 ms 109300 KB Output is correct
5 Correct 23 ms 109404 KB Output is correct
6 Correct 23 ms 109392 KB Output is correct
7 Correct 23 ms 109504 KB Output is correct
8 Correct 23 ms 109404 KB Output is correct
9 Correct 23 ms 109540 KB Output is correct
10 Correct 24 ms 109504 KB Output is correct
11 Correct 23 ms 109404 KB Output is correct
12 Correct 24 ms 109392 KB Output is correct
13 Correct 24 ms 109404 KB Output is correct
14 Correct 23 ms 109404 KB Output is correct
15 Correct 23 ms 109404 KB Output is correct
16 Correct 23 ms 109400 KB Output is correct
17 Correct 23 ms 109404 KB Output is correct
18 Correct 23 ms 109404 KB Output is correct
19 Correct 24 ms 109400 KB Output is correct
20 Correct 23 ms 109404 KB Output is correct
21 Correct 23 ms 109456 KB Output is correct
22 Correct 23 ms 109768 KB Output is correct
23 Correct 24 ms 109520 KB Output is correct
24 Correct 23 ms 109404 KB Output is correct
25 Correct 24 ms 109292 KB Output is correct
26 Correct 24 ms 109764 KB Output is correct
27 Correct 107 ms 144332 KB Output is correct
28 Correct 108 ms 144336 KB Output is correct
29 Correct 173 ms 146912 KB Output is correct
30 Correct 162 ms 146768 KB Output is correct
31 Correct 153 ms 147036 KB Output is correct
32 Correct 152 ms 146772 KB Output is correct
33 Correct 170 ms 148688 KB Output is correct
34 Correct 171 ms 148704 KB Output is correct
35 Correct 158 ms 148840 KB Output is correct
36 Correct 155 ms 148404 KB Output is correct
37 Correct 174 ms 148564 KB Output is correct
38 Correct 173 ms 151124 KB Output is correct
39 Correct 165 ms 151176 KB Output is correct
40 Correct 173 ms 151212 KB Output is correct
41 Correct 173 ms 151096 KB Output is correct
42 Correct 178 ms 153004 KB Output is correct
43 Correct 175 ms 154448 KB Output is correct
44 Correct 172 ms 154452 KB Output is correct
45 Correct 159 ms 157456 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 109392 KB Output is correct
2 Correct 25 ms 109464 KB Output is correct
3 Correct 23 ms 109544 KB Output is correct
4 Correct 23 ms 109300 KB Output is correct
5 Correct 23 ms 109404 KB Output is correct
6 Correct 23 ms 109392 KB Output is correct
7 Correct 23 ms 109504 KB Output is correct
8 Correct 23 ms 109404 KB Output is correct
9 Correct 23 ms 109540 KB Output is correct
10 Correct 24 ms 109504 KB Output is correct
11 Correct 23 ms 109404 KB Output is correct
12 Correct 24 ms 109392 KB Output is correct
13 Correct 24 ms 109404 KB Output is correct
14 Correct 23 ms 109404 KB Output is correct
15 Correct 23 ms 109404 KB Output is correct
16 Correct 23 ms 109400 KB Output is correct
17 Correct 23 ms 109404 KB Output is correct
18 Correct 23 ms 109404 KB Output is correct
19 Correct 24 ms 109400 KB Output is correct
20 Correct 23 ms 109404 KB Output is correct
21 Correct 23 ms 109456 KB Output is correct
22 Correct 23 ms 109768 KB Output is correct
23 Correct 24 ms 109520 KB Output is correct
24 Correct 23 ms 109404 KB Output is correct
25 Correct 24 ms 109292 KB Output is correct
26 Correct 24 ms 109764 KB Output is correct
27 Correct 107 ms 144332 KB Output is correct
28 Correct 108 ms 144336 KB Output is correct
29 Correct 173 ms 146912 KB Output is correct
30 Correct 162 ms 146768 KB Output is correct
31 Correct 153 ms 147036 KB Output is correct
32 Correct 152 ms 146772 KB Output is correct
33 Correct 170 ms 148688 KB Output is correct
34 Correct 171 ms 148704 KB Output is correct
35 Correct 158 ms 148840 KB Output is correct
36 Correct 155 ms 148404 KB Output is correct
37 Correct 174 ms 148564 KB Output is correct
38 Correct 173 ms 151124 KB Output is correct
39 Correct 165 ms 151176 KB Output is correct
40 Correct 173 ms 151212 KB Output is correct
41 Correct 173 ms 151096 KB Output is correct
42 Correct 178 ms 153004 KB Output is correct
43 Correct 175 ms 154448 KB Output is correct
44 Correct 172 ms 154452 KB Output is correct
45 Correct 159 ms 157456 KB Output is correct
46 Correct 172 ms 151124 KB Output is correct
47 Correct 2590 ms 725864 KB Output is correct
48 Correct 2701 ms 730204 KB Output is correct
49 Correct 2877 ms 747732 KB Output is correct
50 Correct 2854 ms 734132 KB Output is correct
51 Correct 2844 ms 734752 KB Output is correct
52 Correct 3176 ms 777384 KB Output is correct
53 Correct 3160 ms 781408 KB Output is correct
54 Correct 3144 ms 774592 KB Output is correct
55 Correct 3189 ms 779360 KB Output is correct
56 Correct 3235 ms 780820 KB Output is correct
57 Correct 3326 ms 777792 KB Output is correct
58 Correct 3440 ms 775856 KB Output is correct
59 Correct 3485 ms 781252 KB Output is correct
60 Correct 3430 ms 774372 KB Output is correct
61 Correct 3487 ms 770444 KB Output is correct
62 Correct 3482 ms 757520 KB Output is correct
63 Correct 3523 ms 742792 KB Output is correct
64 Correct 2301 ms 825144 KB Output is correct
65 Correct 2332 ms 825112 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 109392 KB Output is correct
2 Correct 25 ms 109464 KB Output is correct
3 Correct 23 ms 109544 KB Output is correct
4 Correct 23 ms 109300 KB Output is correct
5 Correct 23 ms 109404 KB Output is correct
6 Correct 23 ms 109392 KB Output is correct
7 Correct 23 ms 109504 KB Output is correct
8 Correct 23 ms 109404 KB Output is correct
9 Correct 23 ms 109540 KB Output is correct
10 Correct 24 ms 109504 KB Output is correct
11 Correct 23 ms 109404 KB Output is correct
12 Correct 24 ms 109392 KB Output is correct
13 Correct 24 ms 109404 KB Output is correct
14 Correct 23 ms 109404 KB Output is correct
15 Correct 23 ms 109404 KB Output is correct
16 Correct 23 ms 109400 KB Output is correct
17 Correct 23 ms 109404 KB Output is correct
18 Correct 23 ms 109404 KB Output is correct
19 Correct 24 ms 109400 KB Output is correct
20 Correct 23 ms 109404 KB Output is correct
21 Correct 23 ms 109456 KB Output is correct
22 Correct 23 ms 109768 KB Output is correct
23 Correct 24 ms 109520 KB Output is correct
24 Correct 23 ms 109404 KB Output is correct
25 Correct 24 ms 109292 KB Output is correct
26 Correct 24 ms 109764 KB Output is correct
27 Correct 107 ms 144332 KB Output is correct
28 Correct 108 ms 144336 KB Output is correct
29 Correct 173 ms 146912 KB Output is correct
30 Correct 162 ms 146768 KB Output is correct
31 Correct 153 ms 147036 KB Output is correct
32 Correct 152 ms 146772 KB Output is correct
33 Correct 170 ms 148688 KB Output is correct
34 Correct 171 ms 148704 KB Output is correct
35 Correct 158 ms 148840 KB Output is correct
36 Correct 155 ms 148404 KB Output is correct
37 Correct 174 ms 148564 KB Output is correct
38 Correct 173 ms 151124 KB Output is correct
39 Correct 165 ms 151176 KB Output is correct
40 Correct 173 ms 151212 KB Output is correct
41 Correct 173 ms 151096 KB Output is correct
42 Correct 178 ms 153004 KB Output is correct
43 Correct 175 ms 154448 KB Output is correct
44 Correct 172 ms 154452 KB Output is correct
45 Correct 159 ms 157456 KB Output is correct
46 Correct 172 ms 151124 KB Output is correct
47 Correct 2590 ms 725864 KB Output is correct
48 Correct 2701 ms 730204 KB Output is correct
49 Correct 2877 ms 747732 KB Output is correct
50 Correct 2854 ms 734132 KB Output is correct
51 Correct 2844 ms 734752 KB Output is correct
52 Correct 3176 ms 777384 KB Output is correct
53 Correct 3160 ms 781408 KB Output is correct
54 Correct 3144 ms 774592 KB Output is correct
55 Correct 3189 ms 779360 KB Output is correct
56 Correct 3235 ms 780820 KB Output is correct
57 Correct 3326 ms 777792 KB Output is correct
58 Correct 3440 ms 775856 KB Output is correct
59 Correct 3485 ms 781252 KB Output is correct
60 Correct 3430 ms 774372 KB Output is correct
61 Correct 3487 ms 770444 KB Output is correct
62 Correct 3482 ms 757520 KB Output is correct
63 Correct 3523 ms 742792 KB Output is correct
64 Correct 2301 ms 825144 KB Output is correct
65 Correct 2332 ms 825112 KB Output is correct
66 Correct 112 ms 142504 KB Output is correct
67 Correct 856 ms 278908 KB Output is correct
68 Correct 2288 ms 788720 KB Output is correct
69 Correct 2695 ms 794284 KB Output is correct
70 Correct 3228 ms 818216 KB Output is correct
71 Correct 4453 ms 723636 KB Output is correct
72 Correct 4681 ms 737380 KB Output is correct
73 Correct 5080 ms 776028 KB Output is correct
74 Correct 5112 ms 781228 KB Output is correct
75 Correct 5190 ms 777716 KB Output is correct
76 Correct 4791 ms 746884 KB Output is correct
77 Correct 4729 ms 736308 KB Output is correct
78 Correct 4642 ms 736900 KB Output is correct
79 Correct 5184 ms 783664 KB Output is correct
80 Correct 5238 ms 781812 KB Output is correct
81 Correct 4955 ms 762408 KB Output is correct
82 Correct 5253 ms 781772 KB Output is correct
83 Correct 5139 ms 768980 KB Output is correct
84 Correct 5376 ms 747748 KB Output is correct
85 Correct 4205 ms 826324 KB Output is correct