답안 #43973 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43973	2018-03-29T01:28:58 Z	model_code	Wild Boar (JOI18_wild_boar)	C++14	100 / 100	10722 ms	839180 KB

wild_boar

#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]
   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]
     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]
     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]
     scanf("%lld %lld", &p[i], &q[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	104824 KB	Output is correct
2	Correct	91 ms	104900 KB	Output is correct
3	Correct	97 ms	104900 KB	Output is correct
4	Correct	93 ms	104956 KB	Output is correct
5	Correct	90 ms	105136 KB	Output is correct
6	Correct	82 ms	105136 KB	Output is correct
7	Correct	98 ms	105136 KB	Output is correct
8	Correct	99 ms	105160 KB	Output is correct
9	Correct	90 ms	105160 KB	Output is correct
10	Correct	90 ms	105160 KB	Output is correct
11	Correct	95 ms	105160 KB	Output is correct
12	Correct	98 ms	105160 KB	Output is correct
13	Correct	87 ms	105160 KB	Output is correct
14	Correct	82 ms	105168 KB	Output is correct
15	Correct	90 ms	105168 KB	Output is correct
16	Correct	91 ms	105168 KB	Output is correct
17	Correct	93 ms	105168 KB	Output is correct
18	Correct	100 ms	105168 KB	Output is correct
19	Correct	98 ms	105168 KB	Output is correct
20	Correct	98 ms	105168 KB	Output is correct
21	Correct	94 ms	105168 KB	Output is correct
22	Correct	85 ms	105196 KB	Output is correct
23	Correct	92 ms	105196 KB	Output is correct
24	Correct	95 ms	105280 KB	Output is correct
25	Correct	89 ms	105280 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	104824 KB	Output is correct
2	Correct	91 ms	104900 KB	Output is correct
3	Correct	97 ms	104900 KB	Output is correct
4	Correct	93 ms	104956 KB	Output is correct
5	Correct	90 ms	105136 KB	Output is correct
6	Correct	82 ms	105136 KB	Output is correct
7	Correct	98 ms	105136 KB	Output is correct
8	Correct	99 ms	105160 KB	Output is correct
9	Correct	90 ms	105160 KB	Output is correct
10	Correct	90 ms	105160 KB	Output is correct
11	Correct	95 ms	105160 KB	Output is correct
12	Correct	98 ms	105160 KB	Output is correct
13	Correct	87 ms	105160 KB	Output is correct
14	Correct	82 ms	105168 KB	Output is correct
15	Correct	90 ms	105168 KB	Output is correct
16	Correct	91 ms	105168 KB	Output is correct
17	Correct	93 ms	105168 KB	Output is correct
18	Correct	100 ms	105168 KB	Output is correct
19	Correct	98 ms	105168 KB	Output is correct
20	Correct	98 ms	105168 KB	Output is correct
21	Correct	94 ms	105168 KB	Output is correct
22	Correct	85 ms	105196 KB	Output is correct
23	Correct	92 ms	105196 KB	Output is correct
24	Correct	95 ms	105280 KB	Output is correct
25	Correct	89 ms	105280 KB	Output is correct
26	Correct	96 ms	105488 KB	Output is correct
27	Correct	273 ms	141756 KB	Output is correct
28	Correct	263 ms	141804 KB	Output is correct
29	Correct	456 ms	145444 KB	Output is correct
30	Correct	424 ms	145564 KB	Output is correct
31	Correct	427 ms	145564 KB	Output is correct
32	Correct	444 ms	145564 KB	Output is correct
33	Correct	456 ms	147056 KB	Output is correct
34	Correct	484 ms	147180 KB	Output is correct
35	Correct	379 ms	147180 KB	Output is correct
36	Correct	403 ms	147180 KB	Output is correct
37	Correct	484 ms	147180 KB	Output is correct
38	Correct	461 ms	149320 KB	Output is correct
39	Correct	478 ms	149936 KB	Output is correct
40	Correct	451 ms	149936 KB	Output is correct
41	Correct	428 ms	149936 KB	Output is correct
42	Correct	378 ms	150892 KB	Output is correct
43	Correct	501 ms	151652 KB	Output is correct
44	Correct	468 ms	151660 KB	Output is correct
45	Correct	417 ms	154352 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	104824 KB	Output is correct
2	Correct	91 ms	104900 KB	Output is correct
3	Correct	97 ms	104900 KB	Output is correct
4	Correct	93 ms	104956 KB	Output is correct
5	Correct	90 ms	105136 KB	Output is correct
6	Correct	82 ms	105136 KB	Output is correct
7	Correct	98 ms	105136 KB	Output is correct
8	Correct	99 ms	105160 KB	Output is correct
9	Correct	90 ms	105160 KB	Output is correct
10	Correct	90 ms	105160 KB	Output is correct
11	Correct	95 ms	105160 KB	Output is correct
12	Correct	98 ms	105160 KB	Output is correct
13	Correct	87 ms	105160 KB	Output is correct
14	Correct	82 ms	105168 KB	Output is correct
15	Correct	90 ms	105168 KB	Output is correct
16	Correct	91 ms	105168 KB	Output is correct
17	Correct	93 ms	105168 KB	Output is correct
18	Correct	100 ms	105168 KB	Output is correct
19	Correct	98 ms	105168 KB	Output is correct
20	Correct	98 ms	105168 KB	Output is correct
21	Correct	94 ms	105168 KB	Output is correct
22	Correct	85 ms	105196 KB	Output is correct
23	Correct	92 ms	105196 KB	Output is correct
24	Correct	95 ms	105280 KB	Output is correct
25	Correct	89 ms	105280 KB	Output is correct
26	Correct	96 ms	105488 KB	Output is correct
27	Correct	273 ms	141756 KB	Output is correct
28	Correct	263 ms	141804 KB	Output is correct
29	Correct	456 ms	145444 KB	Output is correct
30	Correct	424 ms	145564 KB	Output is correct
31	Correct	427 ms	145564 KB	Output is correct
32	Correct	444 ms	145564 KB	Output is correct
33	Correct	456 ms	147056 KB	Output is correct
34	Correct	484 ms	147180 KB	Output is correct
35	Correct	379 ms	147180 KB	Output is correct
36	Correct	403 ms	147180 KB	Output is correct
37	Correct	484 ms	147180 KB	Output is correct
38	Correct	461 ms	149320 KB	Output is correct
39	Correct	478 ms	149936 KB	Output is correct
40	Correct	451 ms	149936 KB	Output is correct
41	Correct	428 ms	149936 KB	Output is correct
42	Correct	378 ms	150892 KB	Output is correct
43	Correct	501 ms	151652 KB	Output is correct
44	Correct	468 ms	151660 KB	Output is correct
45	Correct	417 ms	154352 KB	Output is correct
46	Correct	364 ms	154352 KB	Output is correct
47	Correct	4610 ms	718116 KB	Output is correct
48	Correct	4931 ms	724732 KB	Output is correct
49	Correct	5360 ms	744668 KB	Output is correct
50	Correct	5266 ms	744668 KB	Output is correct
51	Correct	5390 ms	744668 KB	Output is correct
52	Correct	5555 ms	771500 KB	Output is correct
53	Correct	5581 ms	775448 KB	Output is correct
54	Correct	5731 ms	775448 KB	Output is correct
55	Correct	5711 ms	775448 KB	Output is correct
56	Correct	6038 ms	775448 KB	Output is correct
57	Correct	5878 ms	775448 KB	Output is correct
58	Correct	6031 ms	775448 KB	Output is correct
59	Correct	6123 ms	777752 KB	Output is correct
60	Correct	6065 ms	777752 KB	Output is correct
61	Correct	6217 ms	777752 KB	Output is correct
62	Correct	6069 ms	777752 KB	Output is correct
63	Correct	6191 ms	777752 KB	Output is correct
64	Correct	3882 ms	821672 KB	Output is correct
65	Correct	3923 ms	822176 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	104824 KB	Output is correct
2	Correct	91 ms	104900 KB	Output is correct
3	Correct	97 ms	104900 KB	Output is correct
4	Correct	93 ms	104956 KB	Output is correct
5	Correct	90 ms	105136 KB	Output is correct
6	Correct	82 ms	105136 KB	Output is correct
7	Correct	98 ms	105136 KB	Output is correct
8	Correct	99 ms	105160 KB	Output is correct
9	Correct	90 ms	105160 KB	Output is correct
10	Correct	90 ms	105160 KB	Output is correct
11	Correct	95 ms	105160 KB	Output is correct
12	Correct	98 ms	105160 KB	Output is correct
13	Correct	87 ms	105160 KB	Output is correct
14	Correct	82 ms	105168 KB	Output is correct
15	Correct	90 ms	105168 KB	Output is correct
16	Correct	91 ms	105168 KB	Output is correct
17	Correct	93 ms	105168 KB	Output is correct
18	Correct	100 ms	105168 KB	Output is correct
19	Correct	98 ms	105168 KB	Output is correct
20	Correct	98 ms	105168 KB	Output is correct
21	Correct	94 ms	105168 KB	Output is correct
22	Correct	85 ms	105196 KB	Output is correct
23	Correct	92 ms	105196 KB	Output is correct
24	Correct	95 ms	105280 KB	Output is correct
25	Correct	89 ms	105280 KB	Output is correct
26	Correct	96 ms	105488 KB	Output is correct
27	Correct	273 ms	141756 KB	Output is correct
28	Correct	263 ms	141804 KB	Output is correct
29	Correct	456 ms	145444 KB	Output is correct
30	Correct	424 ms	145564 KB	Output is correct
31	Correct	427 ms	145564 KB	Output is correct
32	Correct	444 ms	145564 KB	Output is correct
33	Correct	456 ms	147056 KB	Output is correct
34	Correct	484 ms	147180 KB	Output is correct
35	Correct	379 ms	147180 KB	Output is correct
36	Correct	403 ms	147180 KB	Output is correct
37	Correct	484 ms	147180 KB	Output is correct
38	Correct	461 ms	149320 KB	Output is correct
39	Correct	478 ms	149936 KB	Output is correct
40	Correct	451 ms	149936 KB	Output is correct
41	Correct	428 ms	149936 KB	Output is correct
42	Correct	378 ms	150892 KB	Output is correct
43	Correct	501 ms	151652 KB	Output is correct
44	Correct	468 ms	151660 KB	Output is correct
45	Correct	417 ms	154352 KB	Output is correct
46	Correct	364 ms	154352 KB	Output is correct
47	Correct	4610 ms	718116 KB	Output is correct
48	Correct	4931 ms	724732 KB	Output is correct
49	Correct	5360 ms	744668 KB	Output is correct
50	Correct	5266 ms	744668 KB	Output is correct
51	Correct	5390 ms	744668 KB	Output is correct
52	Correct	5555 ms	771500 KB	Output is correct
53	Correct	5581 ms	775448 KB	Output is correct
54	Correct	5731 ms	775448 KB	Output is correct
55	Correct	5711 ms	775448 KB	Output is correct
56	Correct	6038 ms	775448 KB	Output is correct
57	Correct	5878 ms	775448 KB	Output is correct
58	Correct	6031 ms	775448 KB	Output is correct
59	Correct	6123 ms	777752 KB	Output is correct
60	Correct	6065 ms	777752 KB	Output is correct
61	Correct	6217 ms	777752 KB	Output is correct
62	Correct	6069 ms	777752 KB	Output is correct
63	Correct	6191 ms	777752 KB	Output is correct
64	Correct	3882 ms	821672 KB	Output is correct
65	Correct	3923 ms	822176 KB	Output is correct
66	Correct	299 ms	822176 KB	Output is correct
67	Correct	1685 ms	822176 KB	Output is correct
68	Correct	4362 ms	822176 KB	Output is correct
69	Correct	4594 ms	822176 KB	Output is correct
70	Correct	6180 ms	827268 KB	Output is correct
71	Correct	8961 ms	827268 KB	Output is correct
72	Correct	9464 ms	827268 KB	Output is correct
73	Correct	9929 ms	827268 KB	Output is correct
74	Correct	10048 ms	827268 KB	Output is correct
75	Correct	10127 ms	827268 KB	Output is correct
76	Correct	9723 ms	827268 KB	Output is correct
77	Correct	9343 ms	827268 KB	Output is correct
78	Correct	9361 ms	827268 KB	Output is correct
79	Correct	10722 ms	827268 KB	Output is correct
80	Correct	10615 ms	827268 KB	Output is correct
81	Correct	9916 ms	827268 KB	Output is correct
82	Correct	10349 ms	827268 KB	Output is correct
83	Correct	10089 ms	827268 KB	Output is correct
84	Correct	10452 ms	827268 KB	Output is correct
85	Correct	8135 ms	839180 KB	Output is correct

답안 #43973

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 38.0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
38.0 / 38.0