답안 #43983 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43983	2018-03-29T03:49:03 Z	azneye	Wild Boar (JOI18_wild_boar)	C++17	62 / 100	4683 ms	654880 KB

wild_boar

#include <bits/stdc++.h>

using namespace std;

namespace {

#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define RARA(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define VERA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef long long ll;
typedef double dd;
const ll MAX_EDGES = 4004;
const ll INF = 1LL << 60;
vector<ll> to, pred, head, cost;
vector<vector<ll>> rev_adj;
ll dist[MAX_EDGES][MAX_EDGES];
vector<pair<ll, ll>> best_edges[MAX_EDGES][MAX_EDGES / 2]; // edge -> vertex -> (inc edge, dist)
// top 2 shortest distance from edge to vertex

void Min(ll& a, ll b) { a = min(a, b); }

void ComputeDist(ll n, ll m) {
  priority_queue<pair<ll, ll>> pq; // (-dist, edge)
  vector<ll> inc_count(n); // # of edges incident to vertex i processed
  auto calc = [&](ll src_edge) {
    fill(ALL(inc_count), 0);
    dist[src_edge][src_edge] = 0;
    pq.emplace(0, src_edge);
    while (not pq.empty()) {
      const auto cur_dist = -pq.top().first;
      const auto edge = pq.top().second;
      pq.pop();
      if (cur_dist > dist[src_edge][edge])
        continue;
      if (++inc_count[to[edge]] > 2)
        continue;
      best_edges[src_edge][to[edge]].emplace_back(edge, cur_dist);
      for (ll nx_edge = head[to[edge]]; ~nx_edge; nx_edge = pred[nx_edge]) {
        // going back on same edge
        if ((edge ^ nx_edge) == 1)
          continue;
        if (cur_dist + cost[nx_edge] < dist[src_edge][nx_edge]) {
          dist[src_edge][nx_edge] = cur_dist + cost[nx_edge];
          pq.emplace(-dist[src_edge][nx_edge], nx_edge);
        }
      }
    }
  };
  memset(dist, 0x3F, sizeof(dist));
  VEVE(e, 0, m) {
    calc(e);
  }
//  PlnArr(dist, m, m);
}

void Solve(ll) {
  ll n, m, t, l;
  cin >> n >> m >> t >> l;
  assert(t == 1);
  head.resize(n, -1);
//  rev_adj.resize(n);
  VEVE(e, 0, m) {
    ll a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    to.push_back(b);
    cost.push_back(c);
    pred.push_back(head[a]);
    head[a] = SIZE(pred) - 1;
//    rev_adj[b].push_back(head[a]);

    to.push_back(a);
    cost.push_back(c);
    pred.push_back(head[b]);
    head[b] = SIZE(pred) - 1;
//    rev_adj[a].push_back(head[b]);
  }
  m *= 2;
  ComputeDist(n, m);
  vector<ll> supply(l);
  VERA(s, supply) {
    cin >> s;
    --s;
  }
  vector<ll> dp_cur(m), dp_pred(m);
  VEVE(_, 0, t) {
    ll p, q;
    cin >> p >> q;
    --p, --q;
    supply[p] = q;
    fill(ALL(dp_pred), INF);
    for (ll e = head[supply.front()]; ~e; e = pred[e]) {
      dp_pred[e] = cost[e];
    }
    VEVE(i, 1, SIZE(supply)) {
      fill(ALL(dp_cur), INF);
      VEVE(pe, 0, m) {
        if (dp_pred[pe] < INF) {
          VERA(best, best_edges[pe][supply[i]]) {
            Min(dp_cur[best.first], dp_pred[pe] + best.second);
          }
        }
      }
//      DEBUG(dp_cur);
      swap(dp_pred, dp_cur);
    }
    ll res = *min_element(ALL(dp_pred));
    if (res >= INF / 2)
      res = -1;
    cout << res << '\n';
  }
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}

int main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	233 ms	314104 KB	Output is correct
2	Correct	226 ms	314172 KB	Output is correct
3	Correct	229 ms	314284 KB	Output is correct
4	Correct	230 ms	314284 KB	Output is correct
5	Correct	228 ms	314408 KB	Output is correct
6	Correct	226 ms	314408 KB	Output is correct
7	Correct	230 ms	314424 KB	Output is correct
8	Correct	224 ms	314424 KB	Output is correct
9	Correct	230 ms	314424 KB	Output is correct
10	Correct	231 ms	314424 KB	Output is correct
11	Correct	235 ms	314424 KB	Output is correct
12	Correct	230 ms	314424 KB	Output is correct
13	Correct	242 ms	314424 KB	Output is correct
14	Correct	225 ms	314424 KB	Output is correct
15	Correct	232 ms	314424 KB	Output is correct
16	Correct	230 ms	314540 KB	Output is correct
17	Correct	228 ms	314540 KB	Output is correct
18	Correct	225 ms	314540 KB	Output is correct
19	Correct	225 ms	314540 KB	Output is correct
20	Correct	231 ms	314540 KB	Output is correct
21	Correct	226 ms	314540 KB	Output is correct
22	Correct	224 ms	314540 KB	Output is correct
23	Correct	227 ms	314540 KB	Output is correct
24	Correct	226 ms	314540 KB	Output is correct
25	Correct	227 ms	314540 KB	Output is correct

Subtask #2
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	233 ms	314104 KB	Output is correct
2	Correct	226 ms	314172 KB	Output is correct
3	Correct	229 ms	314284 KB	Output is correct
4	Correct	230 ms	314284 KB	Output is correct
5	Correct	228 ms	314408 KB	Output is correct
6	Correct	226 ms	314408 KB	Output is correct
7	Correct	230 ms	314424 KB	Output is correct
8	Correct	224 ms	314424 KB	Output is correct
9	Correct	230 ms	314424 KB	Output is correct
10	Correct	231 ms	314424 KB	Output is correct
11	Correct	235 ms	314424 KB	Output is correct
12	Correct	230 ms	314424 KB	Output is correct
13	Correct	242 ms	314424 KB	Output is correct
14	Correct	225 ms	314424 KB	Output is correct
15	Correct	232 ms	314424 KB	Output is correct
16	Correct	230 ms	314540 KB	Output is correct
17	Correct	228 ms	314540 KB	Output is correct
18	Correct	225 ms	314540 KB	Output is correct
19	Correct	225 ms	314540 KB	Output is correct
20	Correct	231 ms	314540 KB	Output is correct
21	Correct	226 ms	314540 KB	Output is correct
22	Correct	224 ms	314540 KB	Output is correct
23	Correct	227 ms	314540 KB	Output is correct
24	Correct	226 ms	314540 KB	Output is correct
25	Correct	227 ms	314540 KB	Output is correct
26	Correct	239 ms	314540 KB	Output is correct
27	Correct	265 ms	315868 KB	Output is correct
28	Correct	261 ms	316048 KB	Output is correct
29	Correct	408 ms	318888 KB	Output is correct
30	Correct	367 ms	319088 KB	Output is correct
31	Correct	358 ms	319088 KB	Output is correct
32	Correct	360 ms	319088 KB	Output is correct
33	Correct	400 ms	320360 KB	Output is correct
34	Correct	423 ms	320364 KB	Output is correct
35	Correct	360 ms	320364 KB	Output is correct
36	Correct	377 ms	320488 KB	Output is correct
37	Correct	411 ms	320488 KB	Output is correct
38	Correct	417 ms	321768 KB	Output is correct
39	Correct	366 ms	321852 KB	Output is correct
40	Correct	405 ms	321852 KB	Output is correct
41	Correct	440 ms	321852 KB	Output is correct
42	Correct	358 ms	322664 KB	Output is correct
43	Correct	402 ms	323176 KB	Output is correct
44	Correct	406 ms	323176 KB	Output is correct
45	Correct	392 ms	323176 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	233 ms	314104 KB	Output is correct
2	Correct	226 ms	314172 KB	Output is correct
3	Correct	229 ms	314284 KB	Output is correct
4	Correct	230 ms	314284 KB	Output is correct
5	Correct	228 ms	314408 KB	Output is correct
6	Correct	226 ms	314408 KB	Output is correct
7	Correct	230 ms	314424 KB	Output is correct
8	Correct	224 ms	314424 KB	Output is correct
9	Correct	230 ms	314424 KB	Output is correct
10	Correct	231 ms	314424 KB	Output is correct
11	Correct	235 ms	314424 KB	Output is correct
12	Correct	230 ms	314424 KB	Output is correct
13	Correct	242 ms	314424 KB	Output is correct
14	Correct	225 ms	314424 KB	Output is correct
15	Correct	232 ms	314424 KB	Output is correct
16	Correct	230 ms	314540 KB	Output is correct
17	Correct	228 ms	314540 KB	Output is correct
18	Correct	225 ms	314540 KB	Output is correct
19	Correct	225 ms	314540 KB	Output is correct
20	Correct	231 ms	314540 KB	Output is correct
21	Correct	226 ms	314540 KB	Output is correct
22	Correct	224 ms	314540 KB	Output is correct
23	Correct	227 ms	314540 KB	Output is correct
24	Correct	226 ms	314540 KB	Output is correct
25	Correct	227 ms	314540 KB	Output is correct
26	Correct	239 ms	314540 KB	Output is correct
27	Correct	265 ms	315868 KB	Output is correct
28	Correct	261 ms	316048 KB	Output is correct
29	Correct	408 ms	318888 KB	Output is correct
30	Correct	367 ms	319088 KB	Output is correct
31	Correct	358 ms	319088 KB	Output is correct
32	Correct	360 ms	319088 KB	Output is correct
33	Correct	400 ms	320360 KB	Output is correct
34	Correct	423 ms	320364 KB	Output is correct
35	Correct	360 ms	320364 KB	Output is correct
36	Correct	377 ms	320488 KB	Output is correct
37	Correct	411 ms	320488 KB	Output is correct
38	Correct	417 ms	321768 KB	Output is correct
39	Correct	366 ms	321852 KB	Output is correct
40	Correct	405 ms	321852 KB	Output is correct
41	Correct	440 ms	321852 KB	Output is correct
42	Correct	358 ms	322664 KB	Output is correct
43	Correct	402 ms	323176 KB	Output is correct
44	Correct	406 ms	323176 KB	Output is correct
45	Correct	392 ms	323176 KB	Output is correct
46	Correct	401 ms	324852 KB	Output is correct
47	Correct	3682 ms	410144 KB	Output is correct
48	Correct	3807 ms	461608 KB	Output is correct
49	Correct	3999 ms	504296 KB	Output is correct
50	Correct	3935 ms	504448 KB	Output is correct
51	Correct	3922 ms	504448 KB	Output is correct
52	Correct	4163 ms	504452 KB	Output is correct
53	Correct	4178 ms	504452 KB	Output is correct
54	Correct	4231 ms	504452 KB	Output is correct
55	Correct	4193 ms	504452 KB	Output is correct
56	Correct	4683 ms	523084 KB	Output is correct
57	Correct	4556 ms	541956 KB	Output is correct
58	Correct	4466 ms	560592 KB	Output is correct
59	Correct	4528 ms	579524 KB	Output is correct
60	Correct	4510 ms	598320 KB	Output is correct
61	Correct	4575 ms	617264 KB	Output is correct
62	Correct	4632 ms	635900 KB	Output is correct
63	Correct	4523 ms	654880 KB	Output is correct
64	Correct	2065 ms	654880 KB	Output is correct
65	Correct	2082 ms	654880 KB	Output is correct

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	233 ms	314104 KB	Output is correct
2	Correct	226 ms	314172 KB	Output is correct
3	Correct	229 ms	314284 KB	Output is correct
4	Correct	230 ms	314284 KB	Output is correct
5	Correct	228 ms	314408 KB	Output is correct
6	Correct	226 ms	314408 KB	Output is correct
7	Correct	230 ms	314424 KB	Output is correct
8	Correct	224 ms	314424 KB	Output is correct
9	Correct	230 ms	314424 KB	Output is correct
10	Correct	231 ms	314424 KB	Output is correct
11	Correct	235 ms	314424 KB	Output is correct
12	Correct	230 ms	314424 KB	Output is correct
13	Correct	242 ms	314424 KB	Output is correct
14	Correct	225 ms	314424 KB	Output is correct
15	Correct	232 ms	314424 KB	Output is correct
16	Correct	230 ms	314540 KB	Output is correct
17	Correct	228 ms	314540 KB	Output is correct
18	Correct	225 ms	314540 KB	Output is correct
19	Correct	225 ms	314540 KB	Output is correct
20	Correct	231 ms	314540 KB	Output is correct
21	Correct	226 ms	314540 KB	Output is correct
22	Correct	224 ms	314540 KB	Output is correct
23	Correct	227 ms	314540 KB	Output is correct
24	Correct	226 ms	314540 KB	Output is correct
25	Correct	227 ms	314540 KB	Output is correct
26	Correct	239 ms	314540 KB	Output is correct
27	Correct	265 ms	315868 KB	Output is correct
28	Correct	261 ms	316048 KB	Output is correct
29	Correct	408 ms	318888 KB	Output is correct
30	Correct	367 ms	319088 KB	Output is correct
31	Correct	358 ms	319088 KB	Output is correct
32	Correct	360 ms	319088 KB	Output is correct
33	Correct	400 ms	320360 KB	Output is correct
34	Correct	423 ms	320364 KB	Output is correct
35	Correct	360 ms	320364 KB	Output is correct
36	Correct	377 ms	320488 KB	Output is correct
37	Correct	411 ms	320488 KB	Output is correct
38	Correct	417 ms	321768 KB	Output is correct
39	Correct	366 ms	321852 KB	Output is correct
40	Correct	405 ms	321852 KB	Output is correct
41	Correct	440 ms	321852 KB	Output is correct
42	Correct	358 ms	322664 KB	Output is correct
43	Correct	402 ms	323176 KB	Output is correct
44	Correct	406 ms	323176 KB	Output is correct
45	Correct	392 ms	323176 KB	Output is correct
46	Correct	401 ms	324852 KB	Output is correct
47	Correct	3682 ms	410144 KB	Output is correct
48	Correct	3807 ms	461608 KB	Output is correct
49	Correct	3999 ms	504296 KB	Output is correct
50	Correct	3935 ms	504448 KB	Output is correct
51	Correct	3922 ms	504448 KB	Output is correct
52	Correct	4163 ms	504452 KB	Output is correct
53	Correct	4178 ms	504452 KB	Output is correct
54	Correct	4231 ms	504452 KB	Output is correct
55	Correct	4193 ms	504452 KB	Output is correct
56	Correct	4683 ms	523084 KB	Output is correct
57	Correct	4556 ms	541956 KB	Output is correct
58	Correct	4466 ms	560592 KB	Output is correct
59	Correct	4528 ms	579524 KB	Output is correct
60	Correct	4510 ms	598320 KB	Output is correct
61	Correct	4575 ms	617264 KB	Output is correct
62	Correct	4632 ms	635900 KB	Output is correct
63	Correct	4523 ms	654880 KB	Output is correct
64	Correct	2065 ms	654880 KB	Output is correct
65	Correct	2082 ms	654880 KB	Output is correct
66	Runtime error	312 ms	654880 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Halted	0 ms	0 KB	-

답안 #43983

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 35.0 / 35.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 38.0

Subtask #1
12.0 / 12.0

Subtask #2
35.0 / 35.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 38.0