oj.uz

Submission #62647

# Submission time Handle Problem Language Result Execution time Memory
62647 2018-07-29T15:47:32 Z gusfring Wild Boar (JOI18_wild_boar) C++14
62 / 100
 6120 ms 665300 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
 
#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]; 

 
void Min(ll& a, ll b) { a = min(a, b); }
 
void ComputeDist(ll n, ll m) {
  priority_queue<pair<ll, ll>> pq;
  vector<ll> inc_count(n);
  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]) {
        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);
  }
}
 
void Solve(ll) {
  ll n, m, t, l;
  scanf("%lld %lld %lld %lld", &n, &m, &t, &l);
  assert(t == 1);
  head.resize(n, -1);
  VEVE(e, 0, m) {
    ll a, b, c;
    scanf("%lld %lld %lld", &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) {
    scanf("%d", &s);
    --s;
  }
  vector<ll> dp_cur(m), dp_pred(m);
  VEVE(_, 0, t) {
    ll p, q;
    scanf("%lld %lld", &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);
          }
        }
      }
      swap(dp_pred, dp_cur);
    }
    ll res = *min_element(ALL(dp_pred));
    if (res >= INF / 2)
      res = -1;
    printf("%lld\n", res);
  }
}
 
 
int main() {
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}

Compilation message

wild_boar.cpp: In function 'void Solve(ll)':
wild_boar.cpp:81:19: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%d", &s);
                 ~~^
wild_boar.cpp:58: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:63: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:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &s);
     ~~~~~^~~~~~~~~~
wild_boar.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &p, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 314028 KB Output is correct
2 Correct 332 ms 314220 KB Output is correct
3 Correct 326 ms 314220 KB Output is correct
4 Correct 300 ms 314424 KB Output is correct
5 Correct 284 ms 314424 KB Output is correct
6 Correct 304 ms 314424 KB Output is correct
7 Correct 325 ms 314424 KB Output is correct
8 Correct 266 ms 314424 KB Output is correct
9 Correct 290 ms 314444 KB Output is correct
10 Correct 308 ms 314444 KB Output is correct
11 Correct 301 ms 314444 KB Output is correct
12 Correct 310 ms 314444 KB Output is correct
13 Correct 332 ms 314444 KB Output is correct
14 Correct 312 ms 314504 KB Output is correct
15 Correct 291 ms 314640 KB Output is correct
16 Correct 272 ms 314640 KB Output is correct
17 Correct 280 ms 314640 KB Output is correct
18 Correct 315 ms 314640 KB Output is correct
19 Correct 344 ms 314656 KB Output is correct
20 Correct 318 ms 314656 KB Output is correct
21 Correct 307 ms 314656 KB Output is correct
22 Correct 308 ms 314656 KB Output is correct
23 Correct 277 ms 314656 KB Output is correct
24 Correct 298 ms 314676 KB Output is correct
25 Correct 279 ms 314676 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 314028 KB Output is correct
2 Correct 332 ms 314220 KB Output is correct
3 Correct 326 ms 314220 KB Output is correct
4 Correct 300 ms 314424 KB Output is correct
5 Correct 284 ms 314424 KB Output is correct
6 Correct 304 ms 314424 KB Output is correct
7 Correct 325 ms 314424 KB Output is correct
8 Correct 266 ms 314424 KB Output is correct
9 Correct 290 ms 314444 KB Output is correct
10 Correct 308 ms 314444 KB Output is correct
11 Correct 301 ms 314444 KB Output is correct
12 Correct 310 ms 314444 KB Output is correct
13 Correct 332 ms 314444 KB Output is correct
14 Correct 312 ms 314504 KB Output is correct
15 Correct 291 ms 314640 KB Output is correct
16 Correct 272 ms 314640 KB Output is correct
17 Correct 280 ms 314640 KB Output is correct
18 Correct 315 ms 314640 KB Output is correct
19 Correct 344 ms 314656 KB Output is correct
20 Correct 318 ms 314656 KB Output is correct
21 Correct 307 ms 314656 KB Output is correct
22 Correct 308 ms 314656 KB Output is correct
23 Correct 277 ms 314656 KB Output is correct
24 Correct 298 ms 314676 KB Output is correct
25 Correct 279 ms 314676 KB Output is correct
26 Correct 289 ms 314676 KB Output is correct
27 Correct 326 ms 316224 KB Output is correct
28 Correct 354 ms 316400 KB Output is correct
29 Correct 634 ms 319064 KB Output is correct
30 Correct 442 ms 319444 KB Output is correct
31 Correct 453 ms 319528 KB Output is correct
32 Correct 475 ms 319728 KB Output is correct
33 Correct 505 ms 321380 KB Output is correct
34 Correct 469 ms 321812 KB Output is correct
35 Correct 420 ms 321992 KB Output is correct
36 Correct 437 ms 322320 KB Output is correct
37 Correct 577 ms 322588 KB Output is correct
38 Correct 552 ms 324292 KB Output is correct
39 Correct 497 ms 324476 KB Output is correct
40 Correct 552 ms 324804 KB Output is correct
41 Correct 524 ms 325276 KB Output is correct
42 Correct 454 ms 326324 KB Output is correct
43 Correct 512 ms 327280 KB Output is correct
44 Correct 528 ms 327608 KB Output is correct
45 Correct 444 ms 327608 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 314028 KB Output is correct
2 Correct 332 ms 314220 KB Output is correct
3 Correct 326 ms 314220 KB Output is correct
4 Correct 300 ms 314424 KB Output is correct
5 Correct 284 ms 314424 KB Output is correct
6 Correct 304 ms 314424 KB Output is correct
7 Correct 325 ms 314424 KB Output is correct
8 Correct 266 ms 314424 KB Output is correct
9 Correct 290 ms 314444 KB Output is correct
10 Correct 308 ms 314444 KB Output is correct
11 Correct 301 ms 314444 KB Output is correct
12 Correct 310 ms 314444 KB Output is correct
13 Correct 332 ms 314444 KB Output is correct
14 Correct 312 ms 314504 KB Output is correct
15 Correct 291 ms 314640 KB Output is correct
16 Correct 272 ms 314640 KB Output is correct
17 Correct 280 ms 314640 KB Output is correct
18 Correct 315 ms 314640 KB Output is correct
19 Correct 344 ms 314656 KB Output is correct
20 Correct 318 ms 314656 KB Output is correct
21 Correct 307 ms 314656 KB Output is correct
22 Correct 308 ms 314656 KB Output is correct
23 Correct 277 ms 314656 KB Output is correct
24 Correct 298 ms 314676 KB Output is correct
25 Correct 279 ms 314676 KB Output is correct
26 Correct 289 ms 314676 KB Output is correct
27 Correct 326 ms 316224 KB Output is correct
28 Correct 354 ms 316400 KB Output is correct
29 Correct 634 ms 319064 KB Output is correct
30 Correct 442 ms 319444 KB Output is correct
31 Correct 453 ms 319528 KB Output is correct
32 Correct 475 ms 319728 KB Output is correct
33 Correct 505 ms 321380 KB Output is correct
34 Correct 469 ms 321812 KB Output is correct
35 Correct 420 ms 321992 KB Output is correct
36 Correct 437 ms 322320 KB Output is correct
37 Correct 577 ms 322588 KB Output is correct
38 Correct 552 ms 324292 KB Output is correct
39 Correct 497 ms 324476 KB Output is correct
40 Correct 552 ms 324804 KB Output is correct
41 Correct 524 ms 325276 KB Output is correct
42 Correct 454 ms 326324 KB Output is correct
43 Correct 512 ms 327280 KB Output is correct
44 Correct 528 ms 327608 KB Output is correct
45 Correct 444 ms 327608 KB Output is correct
46 Correct 507 ms 329592 KB Output is correct
47 Correct 4478 ms 415244 KB Output is correct
48 Correct 5201 ms 466452 KB Output is correct
49 Correct 5204 ms 509572 KB Output is correct
50 Correct 4785 ms 509880 KB Output is correct
51 Correct 4717 ms 510160 KB Output is correct
52 Correct 4945 ms 510560 KB Output is correct
53 Correct 5312 ms 510932 KB Output is correct
54 Correct 4874 ms 511344 KB Output is correct
55 Correct 5234 ms 511696 KB Output is correct
56 Correct 5024 ms 530692 KB Output is correct
57 Correct 5761 ms 549940 KB Output is correct
58 Correct 5311 ms 569468 KB Output is correct
59 Correct 5867 ms 588424 KB Output is correct
60 Correct 6120 ms 607748 KB Output is correct
61 Correct 5448 ms 626904 KB Output is correct
62 Correct 5638 ms 646104 KB Output is correct
63 Correct 5693 ms 665300 KB Output is correct
64 Correct 2567 ms 665300 KB Output is correct
65 Correct 2869 ms 665300 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 314028 KB Output is correct
2 Correct 332 ms 314220 KB Output is correct
3 Correct 326 ms 314220 KB Output is correct
4 Correct 300 ms 314424 KB Output is correct
5 Correct 284 ms 314424 KB Output is correct
6 Correct 304 ms 314424 KB Output is correct
7 Correct 325 ms 314424 KB Output is correct
8 Correct 266 ms 314424 KB Output is correct
9 Correct 290 ms 314444 KB Output is correct
10 Correct 308 ms 314444 KB Output is correct
11 Correct 301 ms 314444 KB Output is correct
12 Correct 310 ms 314444 KB Output is correct
13 Correct 332 ms 314444 KB Output is correct
14 Correct 312 ms 314504 KB Output is correct
15 Correct 291 ms 314640 KB Output is correct
16 Correct 272 ms 314640 KB Output is correct
17 Correct 280 ms 314640 KB Output is correct
18 Correct 315 ms 314640 KB Output is correct
19 Correct 344 ms 314656 KB Output is correct
20 Correct 318 ms 314656 KB Output is correct
21 Correct 307 ms 314656 KB Output is correct
22 Correct 308 ms 314656 KB Output is correct
23 Correct 277 ms 314656 KB Output is correct
24 Correct 298 ms 314676 KB Output is correct
25 Correct 279 ms 314676 KB Output is correct
26 Correct 289 ms 314676 KB Output is correct
27 Correct 326 ms 316224 KB Output is correct
28 Correct 354 ms 316400 KB Output is correct
29 Correct 634 ms 319064 KB Output is correct
30 Correct 442 ms 319444 KB Output is correct
31 Correct 453 ms 319528 KB Output is correct
32 Correct 475 ms 319728 KB Output is correct
33 Correct 505 ms 321380 KB Output is correct
34 Correct 469 ms 321812 KB Output is correct
35 Correct 420 ms 321992 KB Output is correct
36 Correct 437 ms 322320 KB Output is correct
37 Correct 577 ms 322588 KB Output is correct
38 Correct 552 ms 324292 KB Output is correct
39 Correct 497 ms 324476 KB Output is correct
40 Correct 552 ms 324804 KB Output is correct
41 Correct 524 ms 325276 KB Output is correct
42 Correct 454 ms 326324 KB Output is correct
43 Correct 512 ms 327280 KB Output is correct
44 Correct 528 ms 327608 KB Output is correct
45 Correct 444 ms 327608 KB Output is correct
46 Correct 507 ms 329592 KB Output is correct
47 Correct 4478 ms 415244 KB Output is correct
48 Correct 5201 ms 466452 KB Output is correct
49 Correct 5204 ms 509572 KB Output is correct
50 Correct 4785 ms 509880 KB Output is correct
51 Correct 4717 ms 510160 KB Output is correct
52 Correct 4945 ms 510560 KB Output is correct
53 Correct 5312 ms 510932 KB Output is correct
54 Correct 4874 ms 511344 KB Output is correct
55 Correct 5234 ms 511696 KB Output is correct
56 Correct 5024 ms 530692 KB Output is correct
57 Correct 5761 ms 549940 KB Output is correct
58 Correct 5311 ms 569468 KB Output is correct
59 Correct 5867 ms 588424 KB Output is correct
60 Correct 6120 ms 607748 KB Output is correct
61 Correct 5448 ms 626904 KB Output is correct
62 Correct 5638 ms 646104 KB Output is correct
63 Correct 5693 ms 665300 KB Output is correct
64 Correct 2567 ms 665300 KB Output is correct
65 Correct 2869 ms 665300 KB Output is correct
66 Runtime error 389 ms 665300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
67 Halted 0 ms 0 KB -