Submission #2010912


Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
typedef pair<int, P> P2;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, M, S, T;
vector<P> G[25252];
int dist[25252];
map<int, P> nxt[25252];
map<int, P> ext[25252];

map<int, int> D[25252];
inline int get(int x, int y) {
  if (D[x].find(y) == D[x].end()) return INF;
  return D[x][y];
}
bool f(int X) {
  rep(i, N) D[i].clear();
  priority_queue<P2> q;
  q.push(P2(0, P(S, -1)));
  D[S][-1] = 0;
  while (!q.empty()) {
    int r = q.top()._1, x = q.top()._2._1, e = q.top()._2._2;
    q.pop();
    if (get(x, e) < r) continue;
    if (e == -1) {
      // in
      for (P2 p : nxt[x]) {
        int ne = p._1;
        if (get(x, ne) > r) {
          D[x][ne] = r;
          q.push(P2(r, P(x, ne)));
        }
      }
    }
    else {
      int to = nxt[x][e]._1, len = nxt[x][e]._2;
      if (to != -1 && get(to, e) > r+len) {
        D[to][e] = r+len;
        q.push(P2(r+len, P(to, e)));
      }
      // out
      int over = r+dist[ext[x][e]._1]+ext[x][e]._2;
      if (over <= X && get(x, -1) > r) {
        D[x][-1] = r;
        q.push(P2(r, P(x, -1)));
      }
    }
  }
  return get(T, -1) <= X;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M >> S >> T;
  rep(e, M) {
    int l;
    cin >> l;
    vector<int> s(l), w(l-1);
    rep(i, l) cin >> s[i];
    rep(i, l-1) cin >> w[i];
    rep(i, l-1) {
      G[s[i]].pb(P(s[i+1], w[i]));
      G[s[i+1]].pb(P(s[i], w[i]));
    }
    rep(k, 2) {
      rep(i, l-1) nxt[s[i]][e*2+k] = P(s[i+1], w[i]);
      nxt[s.back()][e*2+k] = P(-1, -1);
      int cost = 0;
      for (int i=l-1; i>=0; i--) {
        if (i < w.size()) cost += w[i];
        ext[s[i]][e*2+k] = P(s.back(), cost);
      }
      reverse(all(s));
      reverse(all(w));
    }
  }
  rep(i, N) dist[i] = INF;
  priority_queue<P> q;
  q.push(P(0, T));
  dist[T] = 0;
  while (!q.empty()) {
    int r = q.top()._1, x = q.top()._2;
    q.pop();
    if (dist[x] < r) continue;
    for (P p : G[x]) {
      int t = p._1, len = p._2;
      if (dist[t] > r+len) {
        dist[t] = r+len;
        q.push(P(dist[t], t));
      }
    }
  }
  int lo = 0, hi = INF;
  while (hi - lo > 1) {
    int mid = (0LL + lo + hi) / 2;
    if (f(mid)) hi = mid;
    else lo = mid;
  }
  cout << hi << "\n";
  return 0;
}

Submission Info

Submission Time
Task C - メンテナンス明け
User funcsr
Language C++14 (GCC 5.4.1)
Score 50
Code Size 2910 Byte
Status TLE
Exec Time 2661 ms
Memory 20772 KB

Judge Result

Set Name Subtask1 Subtask2
Score / Max Score 50 / 50 0 / 50
Status
AC × 52
TLE × 6
Set Name Test Cases
Subtask1 small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05
Subtask2 large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large
Case Name Status Exec Time Memory
large/20_large-00 TLE 2661 ms 18688 KB
large/20_large-01 TLE 2657 ms 20772 KB
large/20_large-02 TLE 2656 ms 20736 KB
large/20_large-03 TLE 2657 ms 18560 KB
large/20_large-04 TLE 2657 ms 18688 KB
large/31_max_large TLE 2657 ms 15420 KB
small/00_sample00 AC 3 ms 4480 KB
small/00_sample01 AC 3 ms 4480 KB
small/00_sample02 AC 3 ms 4480 KB
small/10_small-0000 AC 664 ms 4736 KB
small/10_small-0001 AC 669 ms 4736 KB
small/10_small-0002 AC 217 ms 4736 KB
small/10_small-0003 AC 371 ms 4736 KB
small/10_small-0004 AC 628 ms 4736 KB
small/10_small-0005 AC 411 ms 4736 KB
small/10_small-0006 AC 569 ms 4736 KB
small/10_small-0007 AC 538 ms 4736 KB
small/10_small-0008 AC 581 ms 4736 KB
small/10_small-0009 AC 381 ms 4736 KB
small/10_small-0010 AC 321 ms 4608 KB
small/10_small-0011 AC 745 ms 4736 KB
small/10_small-0012 AC 454 ms 4736 KB
small/10_small-0013 AC 425 ms 4736 KB
small/10_small-0014 AC 532 ms 4736 KB
small/10_small-0015 AC 606 ms 4736 KB
small/10_small-0016 AC 356 ms 4608 KB
small/10_small-0017 AC 511 ms 4736 KB
small/10_small-0018 AC 510 ms 4736 KB
small/10_small-0019 AC 299 ms 4608 KB
small/30_max_small AC 62 ms 4608 KB
small/40_simple_0000 AC 3 ms 4480 KB
small/40_simple_0001 AC 3 ms 4480 KB
small/40_simple_0002 AC 3 ms 4480 KB
small/40_simple_0003 AC 3 ms 4480 KB
small/40_simple_0004 AC 3 ms 4480 KB
small/40_simple_0005 AC 3 ms 4480 KB
small/40_simple_0006 AC 3 ms 4480 KB
small/40_simple_0007 AC 3 ms 4480 KB
small/40_simple_0008 AC 3 ms 4480 KB
small/40_simple_0009 AC 3 ms 4480 KB
small/40_simple_0010 AC 3 ms 4480 KB
small/40_simple_0011 AC 3 ms 4480 KB
small/40_simple_0012 AC 3 ms 4480 KB
small/40_simple_0013 AC 3 ms 4480 KB
small/40_simple_0014 AC 3 ms 4480 KB
small/40_simple_0015 AC 3 ms 4480 KB
small/40_simple_0016 AC 3 ms 4480 KB
small/40_simple_0017 AC 3 ms 4480 KB
small/40_simple_0018 AC 3 ms 4480 KB
small/40_simple_0019 AC 3 ms 4480 KB
small/90_dijkstra_killer_00 AC 3 ms 4480 KB
small/90_dijkstra_killer_01 AC 3 ms 4480 KB
small/91_tayama_killer_00 AC 3 ms 4480 KB
small/91_tayama_killer_01 AC 3 ms 4480 KB
small/91_tayama_killer_02 AC 3 ms 4480 KB
small/91_tayama_killer_03 AC 3 ms 4480 KB
small/91_tayama_killer_04 AC 3 ms 4480 KB
small/91_tayama_killer_05 AC 3 ms 4480 KB