oj.uz

Submission #416892

# Submission time Handle Problem Language Result Execution time Memory
416892 2021-06-03T07:00:20 Z Mamnoon_Siam Wild Boar (JOI18_wild_boar) C++17
12 / 100
 594 ms 772552 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 int N = 4e3 + 3;
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[N], B[N], C[N];
vi ine[N], oute[N];
ll cost[N][N]; // cost[i][j] = shortest path from i-th directed edge to j-th directed edge
int X[N];
vector<path> top5[N][N];
vector<path> fn[100005];

#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);
    }
  }
  while(T--) {
    int p, q;
    scanf("%d %d", &p, &q);
    X[p] = q;

    debug(vi(X+1, X+1+L));

    ll ans = inf;
    vector<path> cur = top5[X[1]][X[2]];
    for(int i = 3; i <= L; ++i) {
      cur = merge(cur, top5[X[i-1]][X[i]]);
    }
    for(path& pa : cur) 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:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d %d %d %d", &n, &m, &T, &L);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d %d %d", &A[2*i], &B[2*i], &C[2*i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%d", &X[i]);
      |     ~~~~~^~~~~~~~~~~~~
wild_boar.cpp:146:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     scanf("%d %d", &p, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 379172 KB Output is correct
2 Correct 237 ms 379208 KB Output is correct
3 Correct 238 ms 379212 KB Output is correct
4 Correct 237 ms 379220 KB Output is correct
5 Correct 233 ms 379124 KB Output is correct
6 Correct 227 ms 379216 KB Output is correct
7 Correct 224 ms 379212 KB Output is correct
8 Correct 235 ms 379148 KB Output is correct
9 Correct 227 ms 379204 KB Output is correct
10 Correct 228 ms 379164 KB Output is correct
11 Correct 228 ms 379204 KB Output is correct
12 Correct 227 ms 379224 KB Output is correct
13 Correct 224 ms 379204 KB Output is correct
14 Correct 228 ms 379128 KB Output is correct
15 Correct 227 ms 379204 KB Output is correct
16 Correct 224 ms 379208 KB Output is correct
17 Correct 226 ms 379204 KB Output is correct
18 Correct 222 ms 379108 KB Output is correct
19 Correct 231 ms 379180 KB Output is correct
20 Correct 227 ms 379204 KB Output is correct
21 Correct 224 ms 379216 KB Output is correct
22 Correct 226 ms 379212 KB Output is correct
23 Correct 228 ms 379204 KB Output is correct
24 Correct 228 ms 379176 KB Output is correct
25 Correct 233 ms 379156 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 379172 KB Output is correct
2 Correct 237 ms 379208 KB Output is correct
3 Correct 238 ms 379212 KB Output is correct
4 Correct 237 ms 379220 KB Output is correct
5 Correct 233 ms 379124 KB Output is correct
6 Correct 227 ms 379216 KB Output is correct
7 Correct 224 ms 379212 KB Output is correct
8 Correct 235 ms 379148 KB Output is correct
9 Correct 227 ms 379204 KB Output is correct
10 Correct 228 ms 379164 KB Output is correct
11 Correct 228 ms 379204 KB Output is correct
12 Correct 227 ms 379224 KB Output is correct
13 Correct 224 ms 379204 KB Output is correct
14 Correct 228 ms 379128 KB Output is correct
15 Correct 227 ms 379204 KB Output is correct
16 Correct 224 ms 379208 KB Output is correct
17 Correct 226 ms 379204 KB Output is correct
18 Correct 222 ms 379108 KB Output is correct
19 Correct 231 ms 379180 KB Output is correct
20 Correct 227 ms 379204 KB Output is correct
21 Correct 224 ms 379216 KB Output is correct
22 Correct 226 ms 379212 KB Output is correct
23 Correct 228 ms 379204 KB Output is correct
24 Correct 228 ms 379176 KB Output is correct
25 Correct 233 ms 379156 KB Output is correct
26 Correct 234 ms 379440 KB Output is correct
27 Runtime error 594 ms 772552 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 379172 KB Output is correct
2 Correct 237 ms 379208 KB Output is correct
3 Correct 238 ms 379212 KB Output is correct
4 Correct 237 ms 379220 KB Output is correct
5 Correct 233 ms 379124 KB Output is correct
6 Correct 227 ms 379216 KB Output is correct
7 Correct 224 ms 379212 KB Output is correct
8 Correct 235 ms 379148 KB Output is correct
9 Correct 227 ms 379204 KB Output is correct
10 Correct 228 ms 379164 KB Output is correct
11 Correct 228 ms 379204 KB Output is correct
12 Correct 227 ms 379224 KB Output is correct
13 Correct 224 ms 379204 KB Output is correct
14 Correct 228 ms 379128 KB Output is correct
15 Correct 227 ms 379204 KB Output is correct
16 Correct 224 ms 379208 KB Output is correct
17 Correct 226 ms 379204 KB Output is correct
18 Correct 222 ms 379108 KB Output is correct
19 Correct 231 ms 379180 KB Output is correct
20 Correct 227 ms 379204 KB Output is correct
21 Correct 224 ms 379216 KB Output is correct
22 Correct 226 ms 379212 KB Output is correct
23 Correct 228 ms 379204 KB Output is correct
24 Correct 228 ms 379176 KB Output is correct
25 Correct 233 ms 379156 KB Output is correct
26 Correct 234 ms 379440 KB Output is correct
27 Runtime error 594 ms 772552 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 379172 KB Output is correct
2 Correct 237 ms 379208 KB Output is correct
3 Correct 238 ms 379212 KB Output is correct
4 Correct 237 ms 379220 KB Output is correct
5 Correct 233 ms 379124 KB Output is correct
6 Correct 227 ms 379216 KB Output is correct
7 Correct 224 ms 379212 KB Output is correct
8 Correct 235 ms 379148 KB Output is correct
9 Correct 227 ms 379204 KB Output is correct
10 Correct 228 ms 379164 KB Output is correct
11 Correct 228 ms 379204 KB Output is correct
12 Correct 227 ms 379224 KB Output is correct
13 Correct 224 ms 379204 KB Output is correct
14 Correct 228 ms 379128 KB Output is correct
15 Correct 227 ms 379204 KB Output is correct
16 Correct 224 ms 379208 KB Output is correct
17 Correct 226 ms 379204 KB Output is correct
18 Correct 222 ms 379108 KB Output is correct
19 Correct 231 ms 379180 KB Output is correct
20 Correct 227 ms 379204 KB Output is correct
21 Correct 224 ms 379216 KB Output is correct
22 Correct 226 ms 379212 KB Output is correct
23 Correct 228 ms 379204 KB Output is correct
24 Correct 228 ms 379176 KB Output is correct
25 Correct 233 ms 379156 KB Output is correct
26 Correct 234 ms 379440 KB Output is correct
27 Runtime error 594 ms 772552 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -