| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58208 |
2018-07-17T07:23:21 Z |
King Suryal(#1687) |
Wild Boar (JOI18_wild_boar) |
C++11 |
|
456 ms |
334556 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
const llong inf = 1e16;
int n, m, T, L;
struct _edge {
int x, c, i;
_edge(int x, int c, int i) : x(x), c(c), i(i) {}
};
vector<_edge> edge[2001];
int a[2000];
int b[2000];
int c[2000];
llong dist[4000][2000][2];
int used[4000][2000][2];
struct pqNode {
int x, t;
llong c;
pqNode(int x, int t, llong c) : x(x), t(t), c(c) {}
bool operator<(const pqNode &t) const {
return c > t.c;
}
};
void dijkstra(int se, llong dist[2000][2], int used[2000][2]) {
for (int i = 1; i <= n; ++i) {
dist[i][0] = inf;
dist[i][1] = inf;
used[i][0] = -1;
used[i][1] = -1;
}
int s = (se & 1) ? a[se >> 1] : b[se >> 1];
priority_queue<pqNode> pq;
pq.emplace(s, used[s][0] = (se >> 1), dist[s][0] = c[se >> 1]);
while (!pq.empty()) {
pqNode x = pq.top();
pq.pop();
if (used[x.x][0] != x.t && used[x.x][1] != x.t) continue;
if (used[x.x][0] == x.t && dist[x.x][0] != x.c) continue;
if (used[x.x][1] == x.t && dist[x.x][1] != x.c) continue;
for (_edge i : edge[x.x]) {
if ((i.i >> 1) == x.t) continue;
llong d = x.c + i.c;
if (d < dist[i.x][0]) {
dist[i.x][1] = dist[i.x][0];
used[i.x][1] = dist[i.x][1];
pq.emplace(i.x, used[i.x][0] = (i.i >> 1), dist[i.x][0] = d);
}
else if (used[i.x][0] != (i.i >> 1) && d < dist[i.x][1]) {
pq.emplace(i.x, used[i.x][1] = (i.i >> 1), dist[i.x][1] = d);
}
}
}
}
struct _distData {
int sx, ex;
llong c;
_distData() : c(inf) {}
_distData(int sx, int ex, llong c)
: sx(sx), ex(ex), c(c) {}
_distData operator+(const _distData &x) const {
if (ex == x.sx) return _distData();
llong d = c + x.c;
if (inf <= d) return _distData();
return _distData(sx, x.ex, d);
}
};
struct distData {
_distData x[5];
void push(int i, _distData p) {
if (i == 0) {
if (p.c < x[0].c) x[0] = p;
}
else if (i == 1) {
if (p.sx == x[0].sx) return;
if (p.c < x[1].c) x[1] = p;
}
else if (i == 2) {
if (p.sx == x[0].sx) return;
if (p.ex == x[1].ex) return;
if (p.c < x[2].c) x[2] = p;
}
else if (i == 3) {
if (p.ex == x[0].ex) return;
if (p.c < x[3].c) x[3] = p;
}
else if (i == 4) {
if (p.ex == x[0].ex) return;
if (p.sx == x[3].sx) return;
if (p.c < x[4].c) x[4] = p;
}
}
void merge(distData &a, distData &b) {
for (int i = 0; i < 4; ++i) x[i] = _distData();
static _distData v[25];
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 5; ++j) {
v[i << 2 | j] = a.x[i] + b.x[j];
}
}
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 25; ++j) {
push(i, v[j]);
}
}
}
} dst[2001][2001], seg[1 << 18];
int xs[100001];
void update(int i, int s, int e, int x) {
if (s + 1 == e) {
seg[i] = dst[xs[x]][xs[x + 1]];
return;
}
int m = (s + e) / 2;
if (x < m) update(i << 1, s, m, x);
else update(i << 1 | 1, m, e, x);
seg[i].merge(seg[i << 1], seg[i << 1 | 1]);
}
int main() {
scanf("%d%d%d%d", &n, &m, &T, &L);
for (int i = 0; i < m; ++i) {
scanf("%d%d%d", a + i, b + i, c + i);
edge[a[i]].emplace_back(b[i], c[i], i << 1);
edge[b[i]].emplace_back(a[i], c[i], i << 1 | 1);
}
for (int i = 0; i < (m << 1); ++i) {
dijkstra(i, dist[i], used[i]);
}
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < (m << 1); ++j) {
int s = (j & 1) ? b[j >> 1] : a[j >> 1];
for (int k = 1; k <= n; ++k) {
dst[s][k].push(i, _distData(j >> 1, used[j][k][0], dist[j][k][0]));
dst[s][k].push(i, _distData(j >> 1, used[j][k][1], dist[j][k][1]));
}
}
}
for (int i = 1; i <= L; ++i) {
scanf("%d", xs + i);
}
for (int i = 1; i < L; ++i) {
update(1, 1, L, i);
}
for (int i = 0; i < T; ++i) {
int p, q;
scanf("%d%d", &p, &q);
xs[p] = q;
if (p < L) update(1, 1, L, p);
if (p > 1) update(1, 1, L, p - 1);
llong ans = seg[1].x[0].c;
printf("%lld\n", ans < inf ? ans : -1);
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:144:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &m, &T, &L);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:146:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", a + i, b + i, c + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", xs + i);
~~~~~^~~~~~~~~~~~~~
wild_boar.cpp:171:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &p, &q);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
456 ms |
334336 KB |
Output is correct |
| 2 |
Incorrect |
291 ms |
334556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
456 ms |
334336 KB |
Output is correct |
| 2 |
Incorrect |
291 ms |
334556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
456 ms |
334336 KB |
Output is correct |
| 2 |
Incorrect |
291 ms |
334556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
456 ms |
334336 KB |
Output is correct |
| 2 |
Incorrect |
291 ms |
334556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
