oj.uz

Submission #231233

# Submission time Handle Problem Language Result Execution time Memory
231233 2020-05-13T05:53:56 Z xiaowuc1 Wild Boar (JOI18_wild_boar) C++14
100 / 100
 8996 ms 602340 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(4);
  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 136 ms 236028 KB Output is correct
2 Correct 147 ms 236032 KB Output is correct
3 Correct 138 ms 236024 KB Output is correct
4 Correct 141 ms 236024 KB Output is correct
5 Correct 137 ms 236024 KB Output is correct
6 Correct 145 ms 236024 KB Output is correct
7 Correct 138 ms 236024 KB Output is correct
8 Correct 141 ms 236024 KB Output is correct
9 Correct 182 ms 236024 KB Output is correct
10 Correct 144 ms 236024 KB Output is correct
11 Correct 148 ms 236024 KB Output is correct
12 Correct 134 ms 236092 KB Output is correct
13 Correct 132 ms 236024 KB Output is correct
14 Correct 132 ms 236024 KB Output is correct
15 Correct 133 ms 235984 KB Output is correct
16 Correct 137 ms 236024 KB Output is correct
17 Correct 138 ms 236024 KB Output is correct
18 Correct 135 ms 236152 KB Output is correct
19 Correct 128 ms 236024 KB Output is correct
20 Correct 130 ms 236024 KB Output is correct
21 Correct 129 ms 236028 KB Output is correct
22 Correct 135 ms 236072 KB Output is correct
23 Correct 135 ms 236024 KB Output is correct
24 Correct 132 ms 236024 KB Output is correct
25 Correct 139 ms 236024 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 236028 KB Output is correct
2 Correct 147 ms 236032 KB Output is correct
3 Correct 138 ms 236024 KB Output is correct
4 Correct 141 ms 236024 KB Output is correct
5 Correct 137 ms 236024 KB Output is correct
6 Correct 145 ms 236024 KB Output is correct
7 Correct 138 ms 236024 KB Output is correct
8 Correct 141 ms 236024 KB Output is correct
9 Correct 182 ms 236024 KB Output is correct
10 Correct 144 ms 236024 KB Output is correct
11 Correct 148 ms 236024 KB Output is correct
12 Correct 134 ms 236092 KB Output is correct
13 Correct 132 ms 236024 KB Output is correct
14 Correct 132 ms 236024 KB Output is correct
15 Correct 133 ms 235984 KB Output is correct
16 Correct 137 ms 236024 KB Output is correct
17 Correct 138 ms 236024 KB Output is correct
18 Correct 135 ms 236152 KB Output is correct
19 Correct 128 ms 236024 KB Output is correct
20 Correct 130 ms 236024 KB Output is correct
21 Correct 129 ms 236028 KB Output is correct
22 Correct 135 ms 236072 KB Output is correct
23 Correct 135 ms 236024 KB Output is correct
24 Correct 132 ms 236024 KB Output is correct
25 Correct 139 ms 236024 KB Output is correct
26 Correct 146 ms 236152 KB Output is correct
27 Correct 156 ms 241016 KB Output is correct
28 Correct 155 ms 240760 KB Output is correct
29 Correct 280 ms 245176 KB Output is correct
30 Correct 277 ms 245348 KB Output is correct
31 Correct 287 ms 245228 KB Output is correct
32 Correct 286 ms 245424 KB Output is correct
33 Correct 277 ms 246392 KB Output is correct
34 Correct 271 ms 246340 KB Output is correct
35 Correct 264 ms 246488 KB Output is correct
36 Correct 272 ms 246520 KB Output is correct
37 Correct 291 ms 246520 KB Output is correct
38 Correct 278 ms 248124 KB Output is correct
39 Correct 281 ms 248060 KB Output is correct
40 Correct 290 ms 248032 KB Output is correct
41 Correct 288 ms 248056 KB Output is correct
42 Correct 292 ms 249336 KB Output is correct
43 Correct 275 ms 250104 KB Output is correct
44 Correct 280 ms 250104 KB Output is correct
45 Correct 200 ms 248440 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 236028 KB Output is correct
2 Correct 147 ms 236032 KB Output is correct
3 Correct 138 ms 236024 KB Output is correct
4 Correct 141 ms 236024 KB Output is correct
5 Correct 137 ms 236024 KB Output is correct
6 Correct 145 ms 236024 KB Output is correct
7 Correct 138 ms 236024 KB Output is correct
8 Correct 141 ms 236024 KB Output is correct
9 Correct 182 ms 236024 KB Output is correct
10 Correct 144 ms 236024 KB Output is correct
11 Correct 148 ms 236024 KB Output is correct
12 Correct 134 ms 236092 KB Output is correct
13 Correct 132 ms 236024 KB Output is correct
14 Correct 132 ms 236024 KB Output is correct
15 Correct 133 ms 235984 KB Output is correct
16 Correct 137 ms 236024 KB Output is correct
17 Correct 138 ms 236024 KB Output is correct
18 Correct 135 ms 236152 KB Output is correct
19 Correct 128 ms 236024 KB Output is correct
20 Correct 130 ms 236024 KB Output is correct
21 Correct 129 ms 236028 KB Output is correct
22 Correct 135 ms 236072 KB Output is correct
23 Correct 135 ms 236024 KB Output is correct
24 Correct 132 ms 236024 KB Output is correct
25 Correct 139 ms 236024 KB Output is correct
26 Correct 146 ms 236152 KB Output is correct
27 Correct 156 ms 241016 KB Output is correct
28 Correct 155 ms 240760 KB Output is correct
29 Correct 280 ms 245176 KB Output is correct
30 Correct 277 ms 245348 KB Output is correct
31 Correct 287 ms 245228 KB Output is correct
32 Correct 286 ms 245424 KB Output is correct
33 Correct 277 ms 246392 KB Output is correct
34 Correct 271 ms 246340 KB Output is correct
35 Correct 264 ms 246488 KB Output is correct
36 Correct 272 ms 246520 KB Output is correct
37 Correct 291 ms 246520 KB Output is correct
38 Correct 278 ms 248124 KB Output is correct
39 Correct 281 ms 248060 KB Output is correct
40 Correct 290 ms 248032 KB Output is correct
41 Correct 288 ms 248056 KB Output is correct
42 Correct 292 ms 249336 KB Output is correct
43 Correct 275 ms 250104 KB Output is correct
44 Correct 280 ms 250104 KB Output is correct
45 Correct 200 ms 248440 KB Output is correct
46 Correct 357 ms 248312 KB Output is correct
47 Correct 6694 ms 554584 KB Output is correct
48 Correct 6173 ms 551868 KB Output is correct
49 Correct 5374 ms 578532 KB Output is correct
50 Correct 5592 ms 566828 KB Output is correct
51 Correct 6085 ms 565360 KB Output is correct
52 Correct 4292 ms 592124 KB Output is correct
53 Correct 4308 ms 594864 KB Output is correct
54 Correct 4326 ms 590728 KB Output is correct
55 Correct 4363 ms 593272 KB Output is correct
56 Correct 4380 ms 596088 KB Output is correct
57 Correct 4416 ms 595904 KB Output is correct
58 Correct 4310 ms 597240 KB Output is correct
59 Correct 4291 ms 601568 KB Output is correct
60 Correct 4191 ms 598016 KB Output is correct
61 Correct 4169 ms 597264 KB Output is correct
62 Correct 3979 ms 589668 KB Output is correct
63 Correct 3964 ms 581248 KB Output is correct
64 Correct 1960 ms 573884 KB Output is correct
65 Correct 1864 ms 574472 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 236028 KB Output is correct
2 Correct 147 ms 236032 KB Output is correct
3 Correct 138 ms 236024 KB Output is correct
4 Correct 141 ms 236024 KB Output is correct
5 Correct 137 ms 236024 KB Output is correct
6 Correct 145 ms 236024 KB Output is correct
7 Correct 138 ms 236024 KB Output is correct
8 Correct 141 ms 236024 KB Output is correct
9 Correct 182 ms 236024 KB Output is correct
10 Correct 144 ms 236024 KB Output is correct
11 Correct 148 ms 236024 KB Output is correct
12 Correct 134 ms 236092 KB Output is correct
13 Correct 132 ms 236024 KB Output is correct
14 Correct 132 ms 236024 KB Output is correct
15 Correct 133 ms 235984 KB Output is correct
16 Correct 137 ms 236024 KB Output is correct
17 Correct 138 ms 236024 KB Output is correct
18 Correct 135 ms 236152 KB Output is correct
19 Correct 128 ms 236024 KB Output is correct
20 Correct 130 ms 236024 KB Output is correct
21 Correct 129 ms 236028 KB Output is correct
22 Correct 135 ms 236072 KB Output is correct
23 Correct 135 ms 236024 KB Output is correct
24 Correct 132 ms 236024 KB Output is correct
25 Correct 139 ms 236024 KB Output is correct
26 Correct 146 ms 236152 KB Output is correct
27 Correct 156 ms 241016 KB Output is correct
28 Correct 155 ms 240760 KB Output is correct
29 Correct 280 ms 245176 KB Output is correct
30 Correct 277 ms 245348 KB Output is correct
31 Correct 287 ms 245228 KB Output is correct
32 Correct 286 ms 245424 KB Output is correct
33 Correct 277 ms 246392 KB Output is correct
34 Correct 271 ms 246340 KB Output is correct
35 Correct 264 ms 246488 KB Output is correct
36 Correct 272 ms 246520 KB Output is correct
37 Correct 291 ms 246520 KB Output is correct
38 Correct 278 ms 248124 KB Output is correct
39 Correct 281 ms 248060 KB Output is correct
40 Correct 290 ms 248032 KB Output is correct
41 Correct 288 ms 248056 KB Output is correct
42 Correct 292 ms 249336 KB Output is correct
43 Correct 275 ms 250104 KB Output is correct
44 Correct 280 ms 250104 KB Output is correct
45 Correct 200 ms 248440 KB Output is correct
46 Correct 357 ms 248312 KB Output is correct
47 Correct 6694 ms 554584 KB Output is correct
48 Correct 6173 ms 551868 KB Output is correct
49 Correct 5374 ms 578532 KB Output is correct
50 Correct 5592 ms 566828 KB Output is correct
51 Correct 6085 ms 565360 KB Output is correct
52 Correct 4292 ms 592124 KB Output is correct
53 Correct 4308 ms 594864 KB Output is correct
54 Correct 4326 ms 590728 KB Output is correct
55 Correct 4363 ms 593272 KB Output is correct
56 Correct 4380 ms 596088 KB Output is correct
57 Correct 4416 ms 595904 KB Output is correct
58 Correct 4310 ms 597240 KB Output is correct
59 Correct 4291 ms 601568 KB Output is correct
60 Correct 4191 ms 598016 KB Output is correct
61 Correct 4169 ms 597264 KB Output is correct
62 Correct 3979 ms 589668 KB Output is correct
63 Correct 3964 ms 581248 KB Output is correct
64 Correct 1960 ms 573884 KB Output is correct
65 Correct 1864 ms 574472 KB Output is correct
66 Correct 251 ms 244472 KB Output is correct
67 Correct 768 ms 317432 KB Output is correct
68 Correct 1369 ms 562440 KB Output is correct
69 Correct 1711 ms 563984 KB Output is correct
70 Correct 1882 ms 564344 KB Output is correct
71 Correct 8559 ms 549324 KB Output is correct
72 Correct 8284 ms 561720 KB Output is correct
73 Correct 6013 ms 591108 KB Output is correct
74 Correct 5932 ms 595820 KB Output is correct
75 Correct 5995 ms 592676 KB Output is correct
76 Correct 7223 ms 577088 KB Output is correct
77 Correct 7959 ms 566200 KB Output is correct
78 Correct 8996 ms 563900 KB Output is correct
79 Correct 5994 ms 599608 KB Output is correct
80 Correct 5996 ms 600440 KB Output is correct
81 Correct 6647 ms 589768 KB Output is correct
82 Correct 5779 ms 602340 KB Output is correct
83 Correct 6230 ms 599776 KB Output is correct
84 Correct 5239 ms 584460 KB Output is correct
85 Correct 2698 ms 575736 KB Output is correct