oj.uz

Submission #41575

# Submission time Handle Problem Language Result Execution time Memory
41575 2018-02-19T10:04:43 Z cheater2k Evacuation plan (IZhO18_plan) C++14
100 / 100
 1681 ms 23272 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
const int INF = 1e8 + 100;
typedef pair<int,int> ii;

struct Query { int s; int t; } query[N];

int n, m, k, q;
vector<int> imp;
vector<ii> G[N];
int d[N];
int par[N];
int low[N], high[N];
vector<ii> events, D;

void dijkstra() {
    for (int i = 1; i <= n; ++i) d[i] = INF;
    
    priority_queue < ii, vector<ii>, greater<ii> > pq;
    for (int u : imp) d[u] = 0, pq.push(ii(0, u));

    while(!pq.empty()) {
        ii top = pq.top(); pq.pop();
        int u = top.second, du = top.first;
        if (du != d[u]) continue;

        for (auto e : G[u]) {
            int v = e.second, w = e.first;
            if (d[v] > du + w) pq.push(ii(d[v] = du + w, v));
        }
    }
}

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) { par[anc(p)] = anc(q); }

void solve() {
    for (int i = 1; i <= n; ++i) par[i] = i;
    sort(events.begin(), events.end());

    int ptr = events.size() - 1;
    for (int i = D.size() - 1; i >= 0; --i) {
        int u = D[i].second;
        for (auto e : G[u]) if (d[e.second] >= d[u]) join(u, e.second);
        while(ptr >= 0 && events[ptr].first >= i) {
            int id = events[ptr].second;
            if (anc(query[id].s) == anc(query[id].t)) {
                low[id] = events[ptr].first;
            } else high[id] = events[ptr].first - 1;
            --ptr;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    while(m--) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back(make_pair(w, v));
        G[v].push_back(make_pair(w, u));
    }
    cin >> k;
    for (int i = 1; i <= k; ++i) {
        int x; cin >> x; imp.push_back(x);
    }

    // prepare
    dijkstra();
    for (int i = 1; i <= n; ++i) {
        D.push_back(ii(d[i], i));
    }
    sort(D.begin(), D.end());

    // process queries
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> query[i].s >> query[i].t;
        low[i] = 0;
        high[i] = D.size() - 1;
    }

    while(true) {
        events.clear();
        for (int i = 1; i <= q; ++i) {
            if (low[i] < high[i]) events.push_back(ii((low[i] + high[i] + 1) >> 1, i));
        }
        if (events.empty()) break;

        solve();
    }

    for (int i = 1; i <= q; ++i) {
        printf("%d\n", D[low[i]].first);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 5 ms 2848 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 6 ms 2812 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 6 ms 2808 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 6 ms 2812 KB Output is correct
14 Correct 6 ms 2808 KB Output is correct
15 Correct 6 ms 2812 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 5 ms 2848 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 6 ms 2812 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 6 ms 2808 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 6 ms 2812 KB Output is correct
14 Correct 6 ms 2808 KB Output is correct
15 Correct 6 ms 2812 KB Output is correct
16 Correct 637 ms 11044 KB Output is correct
17 Correct 1581 ms 23000 KB Output is correct
18 Correct 78 ms 5160 KB Output is correct
19 Correct 271 ms 13244 KB Output is correct
20 Correct 1585 ms 22936 KB Output is correct
21 Correct 975 ms 15252 KB Output is correct
22 Correct 558 ms 11628 KB Output is correct
23 Correct 1581 ms 23140 KB Output is correct
24 Correct 1616 ms 23272 KB Output is correct
25 Correct 1665 ms 23188 KB Output is correct
26 Correct 339 ms 13740 KB Output is correct
27 Correct 280 ms 14460 KB Output is correct
28 Correct 303 ms 13612 KB Output is correct
29 Correct 269 ms 13788 KB Output is correct
30 Correct 263 ms 13272 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 4 ms 2680 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 11952 KB Output is correct
2 Correct 1198 ms 20436 KB Output is correct
3 Correct 1247 ms 20480 KB Output is correct
4 Correct 228 ms 8044 KB Output is correct
5 Correct 1176 ms 20392 KB Output is correct
6 Correct 1216 ms 20540 KB Output is correct
7 Correct 1208 ms 20240 KB Output is correct
8 Correct 1233 ms 20324 KB Output is correct
9 Correct 1208 ms 20212 KB Output is correct
10 Correct 1181 ms 20892 KB Output is correct
11 Correct 1186 ms 20808 KB Output is correct
12 Correct 1237 ms 20844 KB Output is correct
13 Correct 1240 ms 20936 KB Output is correct
14 Correct 1212 ms 21364 KB Output is correct
15 Correct 1177 ms 21388 KB Output is correct
16 Correct 1175 ms 21444 KB Output is correct
17 Correct 1204 ms 21328 KB Output is correct
18 Correct 1273 ms 21228 KB Output is correct
19 Correct 229 ms 8692 KB Output is correct
20 Correct 1164 ms 20724 KB Output is correct
21 Correct 1258 ms 20228 KB Output is correct
22 Correct 147 ms 10976 KB Output is correct
23 Correct 201 ms 8168 KB Output is correct
24 Correct 153 ms 10152 KB Output is correct
25 Correct 153 ms 10812 KB Output is correct
26 Correct 211 ms 8168 KB Output is correct
27 Correct 194 ms 7784 KB Output is correct
28 Correct 163 ms 10336 KB Output is correct
29 Correct 169 ms 7660 KB Output is correct
30 Correct 138 ms 10196 KB Output is correct
31 Correct 175 ms 7812 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 5 ms 2848 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 6 ms 2808 KB Output is correct
6 Correct 6 ms 2808 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 4 ms 2680 KB Output is correct
9 Correct 6 ms 2812 KB Output is correct
10 Correct 6 ms 2808 KB Output is correct
11 Correct 6 ms 2808 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct
13 Correct 6 ms 2812 KB Output is correct
14 Correct 6 ms 2808 KB Output is correct
15 Correct 6 ms 2812 KB Output is correct
16 Correct 637 ms 11044 KB Output is correct
17 Correct 1581 ms 23000 KB Output is correct
18 Correct 78 ms 5160 KB Output is correct
19 Correct 271 ms 13244 KB Output is correct
20 Correct 1585 ms 22936 KB Output is correct
21 Correct 975 ms 15252 KB Output is correct
22 Correct 558 ms 11628 KB Output is correct
23 Correct 1581 ms 23140 KB Output is correct
24 Correct 1616 ms 23272 KB Output is correct
25 Correct 1665 ms 23188 KB Output is correct
26 Correct 339 ms 13740 KB Output is correct
27 Correct 280 ms 14460 KB Output is correct
28 Correct 303 ms 13612 KB Output is correct
29 Correct 269 ms 13788 KB Output is correct
30 Correct 263 ms 13272 KB Output is correct
31 Correct 4 ms 2680 KB Output is correct
32 Correct 4 ms 2680 KB Output is correct
33 Correct 4 ms 2680 KB Output is correct
34 Correct 4 ms 2680 KB Output is correct
35 Correct 4 ms 2680 KB Output is correct
36 Correct 4 ms 2680 KB Output is correct
37 Correct 4 ms 2680 KB Output is correct
38 Correct 4 ms 2680 KB Output is correct
39 Correct 4 ms 2680 KB Output is correct
40 Correct 4 ms 2680 KB Output is correct
41 Correct 704 ms 11952 KB Output is correct
42 Correct 1198 ms 20436 KB Output is correct
43 Correct 1247 ms 20480 KB Output is correct
44 Correct 228 ms 8044 KB Output is correct
45 Correct 1176 ms 20392 KB Output is correct
46 Correct 1216 ms 20540 KB Output is correct
47 Correct 1208 ms 20240 KB Output is correct
48 Correct 1233 ms 20324 KB Output is correct
49 Correct 1208 ms 20212 KB Output is correct
50 Correct 1181 ms 20892 KB Output is correct
51 Correct 1186 ms 20808 KB Output is correct
52 Correct 1237 ms 20844 KB Output is correct
53 Correct 1240 ms 20936 KB Output is correct
54 Correct 1212 ms 21364 KB Output is correct
55 Correct 1177 ms 21388 KB Output is correct
56 Correct 1175 ms 21444 KB Output is correct
57 Correct 1204 ms 21328 KB Output is correct
58 Correct 1273 ms 21228 KB Output is correct
59 Correct 229 ms 8692 KB Output is correct
60 Correct 1164 ms 20724 KB Output is correct
61 Correct 1258 ms 20228 KB Output is correct
62 Correct 147 ms 10976 KB Output is correct
63 Correct 201 ms 8168 KB Output is correct
64 Correct 153 ms 10152 KB Output is correct
65 Correct 153 ms 10812 KB Output is correct
66 Correct 211 ms 8168 KB Output is correct
67 Correct 194 ms 7784 KB Output is correct
68 Correct 163 ms 10336 KB Output is correct
69 Correct 169 ms 7660 KB Output is correct
70 Correct 138 ms 10196 KB Output is correct
71 Correct 175 ms 7812 KB Output is correct
72 Correct 1080 ms 14448 KB Output is correct
73 Correct 1608 ms 22704 KB Output is correct
74 Correct 1590 ms 22600 KB Output is correct
75 Correct 1576 ms 22720 KB Output is correct
76 Correct 1563 ms 22652 KB Output is correct
77 Correct 1597 ms 22696 KB Output is correct
78 Correct 1638 ms 22712 KB Output is correct
79 Correct 1657 ms 22824 KB Output is correct
80 Correct 1622 ms 22560 KB Output is correct
81 Correct 1579 ms 22708 KB Output is correct
82 Correct 1554 ms 22552 KB Output is correct
83 Correct 1604 ms 22468 KB Output is correct
84 Correct 1596 ms 22712 KB Output is correct
85 Correct 1645 ms 22628 KB Output is correct
86 Correct 1547 ms 22628 KB Output is correct
87 Correct 1607 ms 22720 KB Output is correct
88 Correct 1601 ms 22724 KB Output is correct
89 Correct 593 ms 11332 KB Output is correct
90 Correct 1594 ms 22584 KB Output is correct
91 Correct 1681 ms 22668 KB Output is correct
92 Correct 274 ms 13140 KB Output is correct
93 Correct 580 ms 11396 KB Output is correct
94 Correct 335 ms 13644 KB Output is correct
95 Correct 293 ms 13504 KB Output is correct
96 Correct 526 ms 10900 KB Output is correct
97 Correct 566 ms 10828 KB Output is correct
98 Correct 366 ms 13172 KB Output is correct
99 Correct 521 ms 10712 KB Output is correct
100 Correct 291 ms 13884 KB Output is correct