oj.uz

Submission #417228

# Submission time Handle Problem Language Result Execution time Memory
417228 2021-06-03T13:33:10 Z dxz05 Evacuation plan (IZhO18_plan) C++14
100 / 100
 3457 ms 332820 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define revall(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.00001;
const int MOD = 998244353;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e5 + 3e2;
const int M = 222;

vector<pair<int, int>> g[N];

int dist[N];
bool processed[N];

int parent[N][750];
int p[N];

int find_set(int x){
    if (p[x] == x) return x;
    return p[x] = find_set(p[x]);
}

void union_sets(int x, int y){
    x = find_set(x);
    y = find_set(y);
    if (x == y) return;
    if (rng() & 1) swap(x, y);
    p[x] = y;
}

int qs[N], qt[N];
vector<int> queries[N];

int ans[N];

void solve(int TC) {
    int n, m;
    cin >> n >> m;

    int SQ = sqrt(m) + 3;

    for (int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    for (int i = 1; i <= n; i++){
        dist[i] = INF;
        p[i] = i;
        for (int j = 0; j < 750; j++) parent[i][j] = i;
    }

    priority_queue<pair<int, int>> pq;
    int k;
    cin >> k;

    while (k--){
        int x;
        cin >> x;
        dist[x] = 0;
        pq.push(MP(0, x));
    }

    while (!pq.empty()){
        int x = pq.top().second; pq.pop();
        if (processed[x]) continue;
        processed[x] = true;
        for (auto edge : g[x]){
            int y = edge.first, w = edge.second;
            if (dist[y] > dist[x] + w){
                dist[y] = dist[x] + w;
                pq.push(MP(-dist[y], y));
            }
        }
    }

    vector<pair<int, pair<int, int>>> edges;

    for (int i = 1; i <= n; i++){
        for (auto edge : g[i]){
            int j = edge.first;
            if (i < j){
                edges.emplace_back(min(dist[i], dist[j]), MP(i, j));
            }
        }
    }

    sort(all(edges));

    for (int i = m - 1; i >= 0; i--){
        int x = edges[i].second.first, y = edges[i].second.second;
        union_sets(x, y);
        if (i % SQ == 0){
            for (int j = 1; j <= n; j++){
                parent[j][i / SQ] = find_set(j);
            }
        }
    }

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++){
        cin >> qs[i] >> qt[i];
        int block = SQ;
        while (parent[qs[i]][block] != parent[qt[i]][block]) block--;
        queries[block].push_back(i);
        ans[i] = 0;
    }

    for (int i = 1; i <= n; i++) p[i] = i;

    for (int i = m - 1; i >= 0; i--){
        int x = edges[i].second.first, y = edges[i].second.second, w = edges[i].first;
        union_sets(x, y);
        for (int j : queries[i / SQ]){
            if (find_set(qs[j]) == find_set(qt[j])) ans[j] = max(ans[j], w);
        }
    }

    for (int i = 1; i <= q; i++){
        cout << ans[i] << endl;
    }

}


int main() {
    startTime = clock();
    cin.tie(nullptr); cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    bool llololcal = false;
#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    llololcal = true;
#endif

    int TC = 1;
    //cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    if (llololcal) cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 7 ms 8012 KB Output is correct
3 Correct 8 ms 8124 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 8 ms 8012 KB Output is correct
6 Correct 8 ms 8012 KB Output is correct
7 Correct 4 ms 5336 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 8 ms 7996 KB Output is correct
10 Correct 8 ms 8128 KB Output is correct
11 Correct 8 ms 8012 KB Output is correct
12 Correct 8 ms 8012 KB Output is correct
13 Correct 8 ms 7996 KB Output is correct
14 Correct 8 ms 8012 KB Output is correct
15 Correct 8 ms 8012 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 7 ms 8012 KB Output is correct
3 Correct 8 ms 8124 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 8 ms 8012 KB Output is correct
6 Correct 8 ms 8012 KB Output is correct
7 Correct 4 ms 5336 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 8 ms 7996 KB Output is correct
10 Correct 8 ms 8128 KB Output is correct
11 Correct 8 ms 8012 KB Output is correct
12 Correct 8 ms 8012 KB Output is correct
13 Correct 8 ms 7996 KB Output is correct
14 Correct 8 ms 8012 KB Output is correct
15 Correct 8 ms 8012 KB Output is correct
16 Correct 1242 ms 244220 KB Output is correct
17 Correct 3070 ms 332144 KB Output is correct
18 Correct 123 ms 44196 KB Output is correct
19 Correct 1331 ms 310612 KB Output is correct
20 Correct 3079 ms 332256 KB Output is correct
21 Correct 1926 ms 315660 KB Output is correct
22 Correct 1270 ms 309480 KB Output is correct
23 Correct 3030 ms 332192 KB Output is correct
24 Correct 2967 ms 332024 KB Output is correct
25 Correct 3058 ms 332072 KB Output is correct
26 Correct 1355 ms 310492 KB Output is correct
27 Correct 1340 ms 310448 KB Output is correct
28 Correct 1339 ms 310460 KB Output is correct
29 Correct 1345 ms 310408 KB Output is correct
30 Correct 1336 ms 310712 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 313068 KB Output is correct
2 Correct 1703 ms 329596 KB Output is correct
3 Correct 1679 ms 329500 KB Output is correct
4 Correct 637 ms 305856 KB Output is correct
5 Correct 1689 ms 329520 KB Output is correct
6 Correct 1653 ms 329540 KB Output is correct
7 Correct 1696 ms 329484 KB Output is correct
8 Correct 1712 ms 329520 KB Output is correct
9 Correct 1722 ms 329440 KB Output is correct
10 Correct 1806 ms 329648 KB Output is correct
11 Correct 1764 ms 329528 KB Output is correct
12 Correct 1762 ms 329524 KB Output is correct
13 Correct 1740 ms 329512 KB Output is correct
14 Correct 1777 ms 329568 KB Output is correct
15 Correct 1810 ms 330364 KB Output is correct
16 Correct 1782 ms 329524 KB Output is correct
17 Correct 1801 ms 329500 KB Output is correct
18 Correct 1832 ms 329536 KB Output is correct
19 Correct 694 ms 305852 KB Output is correct
20 Correct 1815 ms 329664 KB Output is correct
21 Correct 1794 ms 329656 KB Output is correct
22 Correct 704 ms 308272 KB Output is correct
23 Correct 695 ms 306396 KB Output is correct
24 Correct 695 ms 308104 KB Output is correct
25 Correct 716 ms 308016 KB Output is correct
26 Correct 681 ms 306368 KB Output is correct
27 Correct 688 ms 305828 KB Output is correct
28 Correct 699 ms 308024 KB Output is correct
29 Correct 680 ms 305984 KB Output is correct
30 Correct 684 ms 308116 KB Output is correct
31 Correct 682 ms 305864 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 7 ms 8012 KB Output is correct
3 Correct 8 ms 8124 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 8 ms 8012 KB Output is correct
6 Correct 8 ms 8012 KB Output is correct
7 Correct 4 ms 5336 KB Output is correct
8 Correct 3 ms 5324 KB Output is correct
9 Correct 8 ms 7996 KB Output is correct
10 Correct 8 ms 8128 KB Output is correct
11 Correct 8 ms 8012 KB Output is correct
12 Correct 8 ms 8012 KB Output is correct
13 Correct 8 ms 7996 KB Output is correct
14 Correct 8 ms 8012 KB Output is correct
15 Correct 8 ms 8012 KB Output is correct
16 Correct 1242 ms 244220 KB Output is correct
17 Correct 3070 ms 332144 KB Output is correct
18 Correct 123 ms 44196 KB Output is correct
19 Correct 1331 ms 310612 KB Output is correct
20 Correct 3079 ms 332256 KB Output is correct
21 Correct 1926 ms 315660 KB Output is correct
22 Correct 1270 ms 309480 KB Output is correct
23 Correct 3030 ms 332192 KB Output is correct
24 Correct 2967 ms 332024 KB Output is correct
25 Correct 3058 ms 332072 KB Output is correct
26 Correct 1355 ms 310492 KB Output is correct
27 Correct 1340 ms 310448 KB Output is correct
28 Correct 1339 ms 310460 KB Output is correct
29 Correct 1345 ms 310408 KB Output is correct
30 Correct 1336 ms 310712 KB Output is correct
31 Correct 3 ms 5068 KB Output is correct
32 Correct 3 ms 5068 KB Output is correct
33 Correct 3 ms 5068 KB Output is correct
34 Correct 3 ms 5040 KB Output is correct
35 Correct 4 ms 5068 KB Output is correct
36 Correct 3 ms 5040 KB Output is correct
37 Correct 4 ms 5068 KB Output is correct
38 Correct 4 ms 5044 KB Output is correct
39 Correct 4 ms 5068 KB Output is correct
40 Correct 3 ms 5068 KB Output is correct
41 Correct 971 ms 313068 KB Output is correct
42 Correct 1703 ms 329596 KB Output is correct
43 Correct 1679 ms 329500 KB Output is correct
44 Correct 637 ms 305856 KB Output is correct
45 Correct 1689 ms 329520 KB Output is correct
46 Correct 1653 ms 329540 KB Output is correct
47 Correct 1696 ms 329484 KB Output is correct
48 Correct 1712 ms 329520 KB Output is correct
49 Correct 1722 ms 329440 KB Output is correct
50 Correct 1806 ms 329648 KB Output is correct
51 Correct 1764 ms 329528 KB Output is correct
52 Correct 1762 ms 329524 KB Output is correct
53 Correct 1740 ms 329512 KB Output is correct
54 Correct 1777 ms 329568 KB Output is correct
55 Correct 1810 ms 330364 KB Output is correct
56 Correct 1782 ms 329524 KB Output is correct
57 Correct 1801 ms 329500 KB Output is correct
58 Correct 1832 ms 329536 KB Output is correct
59 Correct 694 ms 305852 KB Output is correct
60 Correct 1815 ms 329664 KB Output is correct
61 Correct 1794 ms 329656 KB Output is correct
62 Correct 704 ms 308272 KB Output is correct
63 Correct 695 ms 306396 KB Output is correct
64 Correct 695 ms 308104 KB Output is correct
65 Correct 716 ms 308016 KB Output is correct
66 Correct 681 ms 306368 KB Output is correct
67 Correct 688 ms 305828 KB Output is correct
68 Correct 699 ms 308024 KB Output is correct
69 Correct 680 ms 305984 KB Output is correct
70 Correct 684 ms 308116 KB Output is correct
71 Correct 682 ms 305864 KB Output is correct
72 Correct 2092 ms 315724 KB Output is correct
73 Correct 3226 ms 332176 KB Output is correct
74 Correct 3203 ms 331992 KB Output is correct
75 Correct 3252 ms 332156 KB Output is correct
76 Correct 3218 ms 331980 KB Output is correct
77 Correct 3222 ms 332056 KB Output is correct
78 Correct 3262 ms 332132 KB Output is correct
79 Correct 3222 ms 332052 KB Output is correct
80 Correct 3231 ms 332088 KB Output is correct
81 Correct 3310 ms 332064 KB Output is correct
82 Correct 3279 ms 332172 KB Output is correct
83 Correct 3281 ms 331980 KB Output is correct
84 Correct 3349 ms 331960 KB Output is correct
85 Correct 3457 ms 332820 KB Output is correct
86 Correct 3387 ms 332068 KB Output is correct
87 Correct 3417 ms 332012 KB Output is correct
88 Correct 3320 ms 332084 KB Output is correct
89 Correct 1587 ms 309452 KB Output is correct
90 Correct 3186 ms 332136 KB Output is correct
91 Correct 3131 ms 331992 KB Output is correct
92 Correct 1565 ms 310396 KB Output is correct
93 Correct 1453 ms 309680 KB Output is correct
94 Correct 1537 ms 310308 KB Output is correct
95 Correct 1544 ms 310408 KB Output is correct
96 Correct 1357 ms 309480 KB Output is correct
97 Correct 1525 ms 308924 KB Output is correct
98 Correct 1551 ms 310320 KB Output is correct
99 Correct 1533 ms 308848 KB Output is correct
100 Correct 1549 ms 310664 KB Output is correct