oj.uz

Submission #190915

# Submission time Handle Problem Language Result Execution time Memory
190915 2020-01-14T09:46:27 Z godwind Evacuation plan (IZhO18_plan) C++17
100 / 100
 1528 ms 41932 KB 
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;


#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228



template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}
 
 
random_device rnd;
 
template<typename T> void shuffle(vector< T > &v) {
    for (int i = 1; i < (int)v.size(); ++i) {
        swap(v[rnd() % i], v[i]);
    }
    for (int i = (int)v.size() - 1; i; --i) {
        swap(v[rnd() % i], v[i]);
    }
}

const int N = 100 * 1000 + 228;
const int INF = 1e9 + 228;

int n, m, k, q;
int left[N], right[N], middle[N];
int dist[N], s[N], t[N];
vector<int> order;
vector<int> list[N];
vector< pair<int, int> > g[N];

void GO(vector<int> lalalala) {
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    for (int i : lalalala) {
        dist[i] = 0;
    }
    priority_queue< pair<int, int> > st;
    for (int i : lalalala) {
        st.push({0, i});
    }
    while (!st.empty()) {
        pair<int, int> p = st.top();
        st.pop();
        int v = p.second;
        for (pair<int, int> go : g[v]) {
            int to = go.first, w = go.second;
            if (dist[v] + w < dist[to]) {
                dist[to] = dist[v] + w;
                st.push({-dist[to], to});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        order.push_back(i);
    }
    sort(order.begin(), order.end(), [&] (int i, int j) {
        return dist[i] > dist[j];
    });
}

int p[N], sz[N];


void init() {
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        sz[i] = 1;
    }
}
int getp(int v) {
    if (v == p[v]) return v;
    p[v] = getp(p[v]);
    return p[v];
}
void join(int u, int v) {
    u = getp(u);
    v = getp(v);
    if (u != v) {
        if (sz[u] < sz[v]) {
            p[u] = v;
            sz[v] += sz[u];
        } else {
            p[v] = u;
            sz[u] += sz[v];
        }
    }
}
bool con(int u, int v) {
    return getp(u) == getp(v);
}

bool on[N], done[N];

void proceed() {
    for (int i = 1; i <= n; ++i) {
        on[i] = 0;
    }
    for (int i = 0; i < q; ++i) {
        done[i] = 0;
    }
    init();
    for (int i = 0; i < n; ++i) {
        int v = order[i];
        on[v] = 1;
        for (pair<int, int> to : g[v]) {
            if (on[to.first]) {
                join(v, to.first);
            }
        }
        for (int id : list[i + 1]) {
            if (con(s[id], t[id])) {
                done[id] = 1;
            }
        }
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    cin >> k;
    vector<int> bad(k);
    for (int i = 0; i < k; ++i) {
        cin >> bad[i];
    }
    GO(bad);
    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> s[i] >> t[i];
    }
    for (int i = 0; i < q; ++i) {
        left[i] = 0;
        right[i] = n;
    }
    bool oke = 0;
    while (!oke) {
        for (int i = 0; i <= n; ++i) {
            list[i].clear();
        }
        for (int i = 0; i < q; ++i) {
            middle[i] = (left[i] + right[i]) >> 1;
            list[middle[i]].push_back(i);
        }
        proceed();
        for (int i = 0; i < q; ++i) {
            if (done[i]) {
                right[i] = middle[i];
            } else {
                left[i] = middle[i];
            }
        }
        oke = 1;
        for (int i = 0; i < q; ++i) {
            if (right[i] - left[i] > 1) {
                oke = 0;
                break;
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << dist[order[right[i] - 1]] << '\n';
    }
    return 0;
}
// RU_023


/*

9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5


*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5288 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 5 ms 5244 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct
13 Correct 9 ms 5240 KB Output is correct
14 Correct 10 ms 5368 KB Output is correct
15 Correct 10 ms 5240 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5288 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 5 ms 5244 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct
13 Correct 9 ms 5240 KB Output is correct
14 Correct 10 ms 5368 KB Output is correct
15 Correct 10 ms 5240 KB Output is correct
16 Correct 581 ms 24864 KB Output is correct
17 Correct 1347 ms 41612 KB Output is correct
18 Correct 69 ms 8564 KB Output is correct
19 Correct 295 ms 23132 KB Output is correct
20 Correct 1372 ms 41484 KB Output is correct
21 Correct 829 ms 30148 KB Output is correct
22 Correct 674 ms 25860 KB Output is correct
23 Correct 1395 ms 41348 KB Output is correct
24 Correct 1445 ms 41312 KB Output is correct
25 Correct 1343 ms 41564 KB Output is correct
26 Correct 308 ms 23152 KB Output is correct
27 Correct 300 ms 23000 KB Output is correct
28 Correct 300 ms 22996 KB Output is correct
29 Correct 298 ms 23504 KB Output is correct
30 Correct 284 ms 23380 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 16576 KB Output is correct
2 Correct 1080 ms 29524 KB Output is correct
3 Correct 1072 ms 29600 KB Output is correct
4 Correct 352 ms 11632 KB Output is correct
5 Correct 1265 ms 29568 KB Output is correct
6 Correct 1075 ms 29580 KB Output is correct
7 Correct 1058 ms 29548 KB Output is correct
8 Correct 1078 ms 29568 KB Output is correct
9 Correct 1195 ms 29548 KB Output is correct
10 Correct 1064 ms 29524 KB Output is correct
11 Correct 1045 ms 29688 KB Output is correct
12 Correct 1050 ms 29320 KB Output is correct
13 Correct 1112 ms 29708 KB Output is correct
14 Correct 1052 ms 29640 KB Output is correct
15 Correct 1110 ms 29972 KB Output is correct
16 Correct 1039 ms 29616 KB Output is correct
17 Correct 1089 ms 29596 KB Output is correct
18 Correct 1071 ms 29808 KB Output is correct
19 Correct 345 ms 11760 KB Output is correct
20 Correct 1044 ms 29552 KB Output is correct
21 Correct 894 ms 30320 KB Output is correct
22 Correct 210 ms 12764 KB Output is correct
23 Correct 278 ms 12144 KB Output is correct
24 Correct 213 ms 13020 KB Output is correct
25 Correct 223 ms 12760 KB Output is correct
26 Correct 336 ms 12072 KB Output is correct
27 Correct 422 ms 11632 KB Output is correct
28 Correct 209 ms 12892 KB Output is correct
29 Correct 449 ms 11712 KB Output is correct
30 Correct 201 ms 12916 KB Output is correct
31 Correct 353 ms 11648 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 8 ms 5240 KB Output is correct
3 Correct 8 ms 5240 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 8 ms 5240 KB Output is correct
6 Correct 7 ms 5288 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 8 ms 5240 KB Output is correct
10 Correct 5 ms 5244 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 8 ms 5240 KB Output is correct
13 Correct 9 ms 5240 KB Output is correct
14 Correct 10 ms 5368 KB Output is correct
15 Correct 10 ms 5240 KB Output is correct
16 Correct 581 ms 24864 KB Output is correct
17 Correct 1347 ms 41612 KB Output is correct
18 Correct 69 ms 8564 KB Output is correct
19 Correct 295 ms 23132 KB Output is correct
20 Correct 1372 ms 41484 KB Output is correct
21 Correct 829 ms 30148 KB Output is correct
22 Correct 674 ms 25860 KB Output is correct
23 Correct 1395 ms 41348 KB Output is correct
24 Correct 1445 ms 41312 KB Output is correct
25 Correct 1343 ms 41564 KB Output is correct
26 Correct 308 ms 23152 KB Output is correct
27 Correct 300 ms 23000 KB Output is correct
28 Correct 300 ms 22996 KB Output is correct
29 Correct 298 ms 23504 KB Output is correct
30 Correct 284 ms 23380 KB Output is correct
31 Correct 7 ms 5112 KB Output is correct
32 Correct 6 ms 5112 KB Output is correct
33 Correct 7 ms 5112 KB Output is correct
34 Correct 7 ms 5084 KB Output is correct
35 Correct 8 ms 5112 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 10 ms 5112 KB Output is correct
38 Correct 6 ms 5112 KB Output is correct
39 Correct 6 ms 5112 KB Output is correct
40 Correct 7 ms 5112 KB Output is correct
41 Correct 621 ms 16576 KB Output is correct
42 Correct 1080 ms 29524 KB Output is correct
43 Correct 1072 ms 29600 KB Output is correct
44 Correct 352 ms 11632 KB Output is correct
45 Correct 1265 ms 29568 KB Output is correct
46 Correct 1075 ms 29580 KB Output is correct
47 Correct 1058 ms 29548 KB Output is correct
48 Correct 1078 ms 29568 KB Output is correct
49 Correct 1195 ms 29548 KB Output is correct
50 Correct 1064 ms 29524 KB Output is correct
51 Correct 1045 ms 29688 KB Output is correct
52 Correct 1050 ms 29320 KB Output is correct
53 Correct 1112 ms 29708 KB Output is correct
54 Correct 1052 ms 29640 KB Output is correct
55 Correct 1110 ms 29972 KB Output is correct
56 Correct 1039 ms 29616 KB Output is correct
57 Correct 1089 ms 29596 KB Output is correct
58 Correct 1071 ms 29808 KB Output is correct
59 Correct 345 ms 11760 KB Output is correct
60 Correct 1044 ms 29552 KB Output is correct
61 Correct 894 ms 30320 KB Output is correct
62 Correct 210 ms 12764 KB Output is correct
63 Correct 278 ms 12144 KB Output is correct
64 Correct 213 ms 13020 KB Output is correct
65 Correct 223 ms 12760 KB Output is correct
66 Correct 336 ms 12072 KB Output is correct
67 Correct 422 ms 11632 KB Output is correct
68 Correct 209 ms 12892 KB Output is correct
69 Correct 449 ms 11712 KB Output is correct
70 Correct 201 ms 12916 KB Output is correct
71 Correct 353 ms 11648 KB Output is correct
72 Correct 839 ms 29492 KB Output is correct
73 Correct 1473 ms 41336 KB Output is correct
74 Correct 1352 ms 41404 KB Output is correct
75 Correct 1339 ms 41472 KB Output is correct
76 Correct 1358 ms 41440 KB Output is correct
77 Correct 1334 ms 41216 KB Output is correct
78 Correct 1386 ms 41380 KB Output is correct
79 Correct 1367 ms 41236 KB Output is correct
80 Correct 1368 ms 41128 KB Output is correct
81 Correct 1330 ms 41132 KB Output is correct
82 Correct 1359 ms 41008 KB Output is correct
83 Correct 1344 ms 41208 KB Output is correct
84 Correct 1346 ms 41388 KB Output is correct
85 Correct 1327 ms 41108 KB Output is correct
86 Correct 1395 ms 41032 KB Output is correct
87 Correct 1366 ms 41220 KB Output is correct
88 Correct 1341 ms 41372 KB Output is correct
89 Correct 624 ms 25992 KB Output is correct
90 Correct 1528 ms 41224 KB Output is correct
91 Correct 1192 ms 41932 KB Output is correct
92 Correct 293 ms 23448 KB Output is correct
93 Correct 486 ms 24416 KB Output is correct
94 Correct 309 ms 23340 KB Output is correct
95 Correct 277 ms 23584 KB Output is correct
96 Correct 490 ms 22920 KB Output is correct
97 Correct 561 ms 24680 KB Output is correct
98 Correct 306 ms 23168 KB Output is correct
99 Correct 559 ms 24692 KB Output is correct
100 Correct 302 ms 23128 KB Output is correct