oj.uz

Submission #231231

# Submission time Handle Problem Language Result Execution time Memory
231231 2020-05-13T05:52:45 Z xiaowuc1 Wild Boar (JOI18_wild_boar) C++14
100 / 100
 9334 ms 635684 KB 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_set>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define derr if(1) cerr
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct edge {
  int from, to, w, id;
  edge(){}
  edge(int a, int b, int c, int d) {
    from=a;
    to=b;
    w=c;
    id=d;
  }
};
struct path {
  int f, l;
  ll w;
  path(){clear();}
  path(int a, int b, ll c) {
    f = a;
    l = b;
    w = c;
  }
  void clear() {
    f = -1;
    w=1e18;
  }
  bool valid() {
    return f >= 0;
  }
  bool operator==(const path& p) {
    return f == p.f && l==p.l && w==p.w;
  }
};
const ll INF = 1e14;
vector<int> edges[2000];
edge alledges[4000];
ll dp[4000][4000];
vector<path> bestpaths[2000][2000];
int n, m;

void calculatebestpaths(vector<path>& paths) {
  vector<path> ret(5);
  for(path out: paths) {
    if(out.w < ret[0].w) ret[0] = out;
  }
  // ret[1] doesn't match either edge
  for(path out: paths) {
    if(out.f == ret[0].f) continue;
    if(out.l == ret[0].l) continue;
    if(out.w < ret[1].w) ret[1] = out;
  }
  // ret[2] doesn't match (a, b)
  for(path out: paths) {
    if(out.f == ret[0].f) continue;
    if(out.l == ret[1].l) continue;
    if(out.w < ret[2].w) ret[2] = out;
  }
  // ret[3] doesn't match (b, a)
  for(path out: paths) {
    if(out.l == ret[0].l) continue;
    if(out.f == ret[1].f) continue;
    if(out.w < ret[3].w) ret[3] = out;
  }
  for(int i = 0; i < sz(ret); i++) {
    if(!ret[i].valid()) ret.erase(ret.begin() + i--);
  }
  paths.swap(ret);
}

void merge(vector<path>& ret, const vector<path>& a, const vector<path>& b) {
  ret.clear();
  for(path lhs: a) {
    for(path rhs: b) {
      if(alledges[lhs.l].to != alledges[rhs.f].from) continue;
      if((lhs.l^rhs.f) == 1) continue;
      ret.push_back(path(lhs.f, rhs.l, lhs.w + rhs.w));
    }
  }
  calculatebestpaths(ret);
}

const int KOOSAGA_SZ = 1 << 17;
vector<path> koosagatree[2 * KOOSAGA_SZ];
int numloc;
void upd(int idx) {
  idx += KOOSAGA_SZ;
  // assumes already set
  while(idx > 1) {
    idx /= 2;
    merge(koosagatree[idx], koosagatree[2*idx], koosagatree[2*idx+1]);
  }
}
ll qry() {
  int lhs = KOOSAGA_SZ;
  int rhs = KOOSAGA_SZ + numloc - 2;
  deque<vector<path>> lq, rq;
  while(lhs <= rhs) {
    if(lhs == rhs) {
      lq.push_back(koosagatree[lhs]);
      break;
    }
    if(lhs%2) lq.push_back(koosagatree[lhs++]);
    if(rhs%2==0) rq.push_front(koosagatree[rhs--]);
    lhs /= 2;
    rhs /= 2;
  }
  while(sz(rq)) {
    lq.push_back(rq.front());
    rq.pop_front();
  }
  assert(sz(lq));
  while(sz(lq) > 1) {
    auto a = lq.front(); lq.pop_front();
    auto b = lq.front(); lq.pop_front();
    vector<path> c;
    merge(c, a, b);
    lq.push_front(c);
  }
  if(sz(lq[0]) == 0) return -1;
  return lq[0].front().w;
}

void dijkstra(int srcid) {
  dp[srcid][srcid] = alledges[srcid].w;
  typedef pair<ll, int> pli;
  priority_queue<pli> q;
  q.push({-dp[srcid][srcid], srcid});
  while(sz(q)) {
    ll ww;
    int edgeid;
    tie(ww, edgeid) = q.top(); q.pop();
    ww *= -1;
    if(dp[srcid][edgeid] != ww) continue;
    for(int outid: edges[alledges[edgeid].to]) {
      if((edgeid^outid) == 1) continue;
      if(dp[srcid][outid] > dp[srcid][edgeid] + alledges[outid].w) {
        dp[srcid][outid] = dp[srcid][edgeid] + alledges[outid].w;
        q.push({-dp[srcid][outid], outid});
      }
    }
  }
}

int locs[100000];
void solve() {
  memset(dp, 1, sizeof(dp));
  int t;
  cin >> n >> m >> t >> numloc;
  for(int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    a--; b--;
    alledges[2*i] = edge(a, b, w, 2*i);
    alledges[2*i+1] = edge(b, a, w, 2*i+1);
    edges[a].push_back(2*i);
    edges[b].push_back(2*i+1);
  }
  for(int i = 0; i < 2*m; i++) dijkstra(i);
  for(int i = 0; i < 2*m; i++) {
    int srcnode = alledges[i].from;
    for(int j = 0; j < 2*m; j++) {
      if(dp[i][j] > INF) continue;
      int destnode = alledges[j].to;
      bestpaths[srcnode][destnode].push_back(path(i, j, dp[i][j]));
    }
  }
  for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
    calculatebestpaths(bestpaths[i][j]);
  }
  for(int i = 0; i < numloc; i++) {
    cin >> locs[i];
    locs[i]--;
  }
  for(int i = 0; i + 1 < numloc; i++) {
    koosagatree[KOOSAGA_SZ + i] = bestpaths[locs[i]][locs[i+1]];
  }
  for(int x = KOOSAGA_SZ-1; x > 0; x--) {
    merge(koosagatree[x], koosagatree[2*x], koosagatree[2*x+1]);
  }
  while(t--) {
    int idx, val;
    cin >> idx >> val;
    locs[--idx] = --val;
    if(idx > 0) {
      koosagatree[KOOSAGA_SZ + idx - 1] = bestpaths[locs[idx-1]][locs[idx]];
      upd(idx-1);
    }
    if(idx + 1 < numloc) {
      koosagatree[KOOSAGA_SZ + idx] = bestpaths[locs[idx]][locs[idx+1]];
      upd(idx);
    }
    cout << qry() << "\n";
  }
}

// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 238072 KB Output is correct
2 Correct 128 ms 238072 KB Output is correct
3 Correct 137 ms 238072 KB Output is correct
4 Correct 134 ms 238072 KB Output is correct
5 Correct 137 ms 238072 KB Output is correct
6 Correct 137 ms 238048 KB Output is correct
7 Correct 127 ms 237972 KB Output is correct
8 Correct 142 ms 238072 KB Output is correct
9 Correct 135 ms 238004 KB Output is correct
10 Correct 130 ms 237980 KB Output is correct
11 Correct 131 ms 238000 KB Output is correct
12 Correct 136 ms 238008 KB Output is correct
13 Correct 130 ms 238072 KB Output is correct
14 Correct 136 ms 238072 KB Output is correct
15 Correct 138 ms 237988 KB Output is correct
16 Correct 147 ms 237980 KB Output is correct
17 Correct 126 ms 238072 KB Output is correct
18 Correct 126 ms 238092 KB Output is correct
19 Correct 149 ms 238072 KB Output is correct
20 Correct 125 ms 238072 KB Output is correct
21 Correct 139 ms 238072 KB Output is correct
22 Correct 121 ms 238072 KB Output is correct
23 Correct 125 ms 238072 KB Output is correct
24 Correct 125 ms 238072 KB Output is correct
25 Correct 125 ms 238072 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 238072 KB Output is correct
2 Correct 128 ms 238072 KB Output is correct
3 Correct 137 ms 238072 KB Output is correct
4 Correct 134 ms 238072 KB Output is correct
5 Correct 137 ms 238072 KB Output is correct
6 Correct 137 ms 238048 KB Output is correct
7 Correct 127 ms 237972 KB Output is correct
8 Correct 142 ms 238072 KB Output is correct
9 Correct 135 ms 238004 KB Output is correct
10 Correct 130 ms 237980 KB Output is correct
11 Correct 131 ms 238000 KB Output is correct
12 Correct 136 ms 238008 KB Output is correct
13 Correct 130 ms 238072 KB Output is correct
14 Correct 136 ms 238072 KB Output is correct
15 Correct 138 ms 237988 KB Output is correct
16 Correct 147 ms 237980 KB Output is correct
17 Correct 126 ms 238072 KB Output is correct
18 Correct 126 ms 238092 KB Output is correct
19 Correct 149 ms 238072 KB Output is correct
20 Correct 125 ms 238072 KB Output is correct
21 Correct 139 ms 238072 KB Output is correct
22 Correct 121 ms 238072 KB Output is correct
23 Correct 125 ms 238072 KB Output is correct
24 Correct 125 ms 238072 KB Output is correct
25 Correct 125 ms 238072 KB Output is correct
26 Correct 125 ms 238200 KB Output is correct
27 Correct 144 ms 243064 KB Output is correct
28 Correct 142 ms 242808 KB Output is correct
29 Correct 269 ms 248128 KB Output is correct
30 Correct 265 ms 247672 KB Output is correct
31 Correct 265 ms 247788 KB Output is correct
32 Correct 264 ms 247552 KB Output is correct
33 Correct 265 ms 249680 KB Output is correct
34 Correct 269 ms 249848 KB Output is correct
35 Correct 257 ms 248680 KB Output is correct
36 Correct 259 ms 249084 KB Output is correct
37 Correct 268 ms 249608 KB Output is correct
38 Correct 267 ms 251512 KB Output is correct
39 Correct 259 ms 250872 KB Output is correct
40 Correct 265 ms 251640 KB Output is correct
41 Correct 267 ms 251700 KB Output is correct
42 Correct 252 ms 251768 KB Output is correct
43 Correct 256 ms 253304 KB Output is correct
44 Correct 264 ms 253372 KB Output is correct
45 Correct 187 ms 251640 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 238072 KB Output is correct
2 Correct 128 ms 238072 KB Output is correct
3 Correct 137 ms 238072 KB Output is correct
4 Correct 134 ms 238072 KB Output is correct
5 Correct 137 ms 238072 KB Output is correct
6 Correct 137 ms 238048 KB Output is correct
7 Correct 127 ms 237972 KB Output is correct
8 Correct 142 ms 238072 KB Output is correct
9 Correct 135 ms 238004 KB Output is correct
10 Correct 130 ms 237980 KB Output is correct
11 Correct 131 ms 238000 KB Output is correct
12 Correct 136 ms 238008 KB Output is correct
13 Correct 130 ms 238072 KB Output is correct
14 Correct 136 ms 238072 KB Output is correct
15 Correct 138 ms 237988 KB Output is correct
16 Correct 147 ms 237980 KB Output is correct
17 Correct 126 ms 238072 KB Output is correct
18 Correct 126 ms 238092 KB Output is correct
19 Correct 149 ms 238072 KB Output is correct
20 Correct 125 ms 238072 KB Output is correct
21 Correct 139 ms 238072 KB Output is correct
22 Correct 121 ms 238072 KB Output is correct
23 Correct 125 ms 238072 KB Output is correct
24 Correct 125 ms 238072 KB Output is correct
25 Correct 125 ms 238072 KB Output is correct
26 Correct 125 ms 238200 KB Output is correct
27 Correct 144 ms 243064 KB Output is correct
28 Correct 142 ms 242808 KB Output is correct
29 Correct 269 ms 248128 KB Output is correct
30 Correct 265 ms 247672 KB Output is correct
31 Correct 265 ms 247788 KB Output is correct
32 Correct 264 ms 247552 KB Output is correct
33 Correct 265 ms 249680 KB Output is correct
34 Correct 269 ms 249848 KB Output is correct
35 Correct 257 ms 248680 KB Output is correct
36 Correct 259 ms 249084 KB Output is correct
37 Correct 268 ms 249608 KB Output is correct
38 Correct 267 ms 251512 KB Output is correct
39 Correct 259 ms 250872 KB Output is correct
40 Correct 265 ms 251640 KB Output is correct
41 Correct 267 ms 251700 KB Output is correct
42 Correct 252 ms 251768 KB Output is correct
43 Correct 256 ms 253304 KB Output is correct
44 Correct 264 ms 253372 KB Output is correct
45 Correct 187 ms 251640 KB Output is correct
46 Correct 349 ms 248324 KB Output is correct
47 Correct 6589 ms 554412 KB Output is correct
48 Correct 5976 ms 551736 KB Output is correct
49 Correct 5187 ms 578492 KB Output is correct
50 Correct 5507 ms 566852 KB Output is correct
51 Correct 6021 ms 565320 KB Output is correct
52 Correct 4280 ms 592332 KB Output is correct
53 Correct 4233 ms 595192 KB Output is correct
54 Correct 4252 ms 590312 KB Output is correct
55 Correct 4278 ms 593416 KB Output is correct
56 Correct 4299 ms 595704 KB Output is correct
57 Correct 4366 ms 595392 KB Output is correct
58 Correct 4553 ms 596952 KB Output is correct
59 Correct 4500 ms 601632 KB Output is correct
60 Correct 4435 ms 597896 KB Output is correct
61 Correct 4295 ms 597484 KB Output is correct
62 Correct 4278 ms 589784 KB Output is correct
63 Correct 4075 ms 581752 KB Output is correct
64 Correct 1960 ms 632532 KB Output is correct
65 Correct 1872 ms 632696 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 238072 KB Output is correct
2 Correct 128 ms 238072 KB Output is correct
3 Correct 137 ms 238072 KB Output is correct
4 Correct 134 ms 238072 KB Output is correct
5 Correct 137 ms 238072 KB Output is correct
6 Correct 137 ms 238048 KB Output is correct
7 Correct 127 ms 237972 KB Output is correct
8 Correct 142 ms 238072 KB Output is correct
9 Correct 135 ms 238004 KB Output is correct
10 Correct 130 ms 237980 KB Output is correct
11 Correct 131 ms 238000 KB Output is correct
12 Correct 136 ms 238008 KB Output is correct
13 Correct 130 ms 238072 KB Output is correct
14 Correct 136 ms 238072 KB Output is correct
15 Correct 138 ms 237988 KB Output is correct
16 Correct 147 ms 237980 KB Output is correct
17 Correct 126 ms 238072 KB Output is correct
18 Correct 126 ms 238092 KB Output is correct
19 Correct 149 ms 238072 KB Output is correct
20 Correct 125 ms 238072 KB Output is correct
21 Correct 139 ms 238072 KB Output is correct
22 Correct 121 ms 238072 KB Output is correct
23 Correct 125 ms 238072 KB Output is correct
24 Correct 125 ms 238072 KB Output is correct
25 Correct 125 ms 238072 KB Output is correct
26 Correct 125 ms 238200 KB Output is correct
27 Correct 144 ms 243064 KB Output is correct
28 Correct 142 ms 242808 KB Output is correct
29 Correct 269 ms 248128 KB Output is correct
30 Correct 265 ms 247672 KB Output is correct
31 Correct 265 ms 247788 KB Output is correct
32 Correct 264 ms 247552 KB Output is correct
33 Correct 265 ms 249680 KB Output is correct
34 Correct 269 ms 249848 KB Output is correct
35 Correct 257 ms 248680 KB Output is correct
36 Correct 259 ms 249084 KB Output is correct
37 Correct 268 ms 249608 KB Output is correct
38 Correct 267 ms 251512 KB Output is correct
39 Correct 259 ms 250872 KB Output is correct
40 Correct 265 ms 251640 KB Output is correct
41 Correct 267 ms 251700 KB Output is correct
42 Correct 252 ms 251768 KB Output is correct
43 Correct 256 ms 253304 KB Output is correct
44 Correct 264 ms 253372 KB Output is correct
45 Correct 187 ms 251640 KB Output is correct
46 Correct 349 ms 248324 KB Output is correct
47 Correct 6589 ms 554412 KB Output is correct
48 Correct 5976 ms 551736 KB Output is correct
49 Correct 5187 ms 578492 KB Output is correct
50 Correct 5507 ms 566852 KB Output is correct
51 Correct 6021 ms 565320 KB Output is correct
52 Correct 4280 ms 592332 KB Output is correct
53 Correct 4233 ms 595192 KB Output is correct
54 Correct 4252 ms 590312 KB Output is correct
55 Correct 4278 ms 593416 KB Output is correct
56 Correct 4299 ms 595704 KB Output is correct
57 Correct 4366 ms 595392 KB Output is correct
58 Correct 4553 ms 596952 KB Output is correct
59 Correct 4500 ms 601632 KB Output is correct
60 Correct 4435 ms 597896 KB Output is correct
61 Correct 4295 ms 597484 KB Output is correct
62 Correct 4278 ms 589784 KB Output is correct
63 Correct 4075 ms 581752 KB Output is correct
64 Correct 1960 ms 632532 KB Output is correct
65 Correct 1872 ms 632696 KB Output is correct
66 Correct 208 ms 247672 KB Output is correct
67 Correct 805 ms 335608 KB Output is correct
68 Correct 1453 ms 628288 KB Output is correct
69 Correct 1824 ms 630264 KB Output is correct
70 Correct 2077 ms 632184 KB Output is correct
71 Correct 8613 ms 549460 KB Output is correct
72 Correct 8338 ms 561860 KB Output is correct
73 Correct 6068 ms 594452 KB Output is correct
74 Correct 6129 ms 597364 KB Output is correct
75 Correct 6130 ms 595276 KB Output is correct
76 Correct 7183 ms 577216 KB Output is correct
77 Correct 8057 ms 566212 KB Output is correct
78 Correct 9334 ms 563636 KB Output is correct
79 Correct 6414 ms 601052 KB Output is correct
80 Correct 6068 ms 601756 KB Output is correct
81 Correct 6976 ms 589908 KB Output is correct
82 Correct 6099 ms 603584 KB Output is correct
83 Correct 6663 ms 600184 KB Output is correct
84 Correct 5676 ms 586120 KB Output is correct
85 Correct 2749 ms 635684 KB Output is correct