oj.uz

답안 #919821

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919821 2024-02-01T17:06:19 Z VMaksimoski008 Evacuation plan (IZhO18_plan) C++14
100 / 100
 456 ms 69308 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

struct Edge { 
    int a, b;
    ll w;
    bool operator<(Edge &e) const { return w < e.w; }
};

struct DSU {
    int n, comp;
    vector<int> par, size;

    void config(int _n) {
        n = _n + 1;
        comp = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int get(int u) {
        if(u == par[u]) return u;
        return par[u] = get(par[u]);
    }

    bool uni(int u, int v) {
        u = get(u), v = get(v);

        if(u == v) return false;
        if(size[u] < size[v]) swap(u, v);

        size[u] += size[v];
        par[v] = u;
        comp--;

        return true;
    }

    int getComp() { return comp; }
    int getSize(int u) { return size[get(u)]; }
    bool sameSet(int u, int v) { return get(u) == get(v); }
};

vector<vector<pll> > G;
int depth[maxn+1], up[maxn+1][LOG];
ll mn[maxn+1][LOG];

void dfs(int u, int p) {
    for(int i=1; i<LOG; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
        mn[u][i] = min(mn[u][i-1], mn[up[u][i-1]][i-1]);
    }

    for(auto &[v, w] : G[u]) {
        if(v == p) continue;
        up[v][0] = u;
        mn[v][0] = w;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

ll get_lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);

    ll ans = 1e18;
    int d = depth[a] - depth[b];
    for(int j=LOG-1; j>=0; j--) {
        if(d & (1 << j)) {
            ans = min(ans, mn[a][j]);
            a = up[a][j];
        }
    }

    if(a == b) return ans;

    for(int j=LOG-1; j>=0; j--) {
        if(up[a][j] != up[b][j]) {
            ans = min(ans, mn[a][j]);
            ans = min(ans, mn[b][j]);
            a = up[a][j];
            b = up[b][j];
        }
    }

    return min({ ans, mn[a][0], mn[b][0] });
}

int32_t main() {
    setIO();

    int n, m;
    cin >> n >> m;
    vector<vector<pii> > graph(n+1);
    vector<Edge> edges(m);
    G.resize(n+1);

    for(Edge &e : edges) {
        cin >> e.a >> e.b >> e.w;
        graph[e.a].push_back({ e.b, e.w });
        graph[e.b].push_back({ e.a, e.w });
    }
    
    int spec;
    cin >> spec;

    priority_queue<pll, vector<pll>, greater<pll> > pq;
    vector<bool> vis(n+1);
    vector<ll> dist(n+1, 1e18);

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

    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if(vis[u]) continue;
        vis[u] = 1;

        for(auto &[v, w] : graph[u]) {
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({ dist[v], v });
            }
        }
    }

    for(Edge &e : edges) e.w = min(dist[e.a], dist[e.b]);
    sort(rall(edges));

    DSU dsu;
    dsu.config(n);

    for(Edge &e : edges) {
        if(dsu.uni(e.a, e.b)) {
            G[e.a].push_back({ e.b, e.w });
            G[e.b].push_back({ e.a, e.w });
        }
    }

    dfs(1, 0);

    int q;
    cin >> q;

    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << get_lca(a, b) << '\n';
    }

    return 0;
}

Compilation message

plan.cpp: In function 'void dfs(int, int)':
plan.cpp:81:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |     for(auto &[v, w] : G[u]) {
      |               ^
plan.cpp: In function 'int32_t main()':
plan.cpp:152:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  152 |         for(auto &[v, w] : graph[u]) {
      |                   ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 138 ms 37584 KB Output is correct
17 Correct 382 ms 67776 KB Output is correct
18 Correct 23 ms 9676 KB Output is correct
19 Correct 152 ms 45420 KB Output is correct
20 Correct 390 ms 67780 KB Output is correct
21 Correct 212 ms 50632 KB Output is correct
22 Correct 153 ms 51260 KB Output is correct
23 Correct 393 ms 67528 KB Output is correct
24 Correct 404 ms 67864 KB Output is correct
25 Correct 405 ms 68032 KB Output is correct
26 Correct 141 ms 45372 KB Output is correct
27 Correct 133 ms 45416 KB Output is correct
28 Correct 132 ms 45196 KB Output is correct
29 Correct 138 ms 45412 KB Output is correct
30 Correct 138 ms 45632 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 48588 KB Output is correct
2 Correct 316 ms 66028 KB Output is correct
3 Correct 340 ms 66240 KB Output is correct
4 Correct 110 ms 46416 KB Output is correct
5 Correct 344 ms 66240 KB Output is correct
6 Correct 324 ms 65984 KB Output is correct
7 Correct 328 ms 65984 KB Output is correct
8 Correct 322 ms 66192 KB Output is correct
9 Correct 320 ms 65904 KB Output is correct
10 Correct 330 ms 65984 KB Output is correct
11 Correct 333 ms 66244 KB Output is correct
12 Correct 321 ms 65920 KB Output is correct
13 Correct 347 ms 66348 KB Output is correct
14 Correct 336 ms 65988 KB Output is correct
15 Correct 333 ms 67008 KB Output is correct
16 Correct 361 ms 66432 KB Output is correct
17 Correct 324 ms 65984 KB Output is correct
18 Correct 321 ms 65984 KB Output is correct
19 Correct 120 ms 48980 KB Output is correct
20 Correct 317 ms 65900 KB Output is correct
21 Correct 329 ms 66224 KB Output is correct
22 Correct 98 ms 43844 KB Output is correct
23 Correct 107 ms 43088 KB Output is correct
24 Correct 96 ms 43840 KB Output is correct
25 Correct 93 ms 43844 KB Output is correct
26 Correct 125 ms 44236 KB Output is correct
27 Correct 110 ms 48720 KB Output is correct
28 Correct 97 ms 43952 KB Output is correct
29 Correct 124 ms 47452 KB Output is correct
30 Correct 97 ms 43844 KB Output is correct
31 Correct 112 ms 47396 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 856 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 138 ms 37584 KB Output is correct
17 Correct 382 ms 67776 KB Output is correct
18 Correct 23 ms 9676 KB Output is correct
19 Correct 152 ms 45420 KB Output is correct
20 Correct 390 ms 67780 KB Output is correct
21 Correct 212 ms 50632 KB Output is correct
22 Correct 153 ms 51260 KB Output is correct
23 Correct 393 ms 67528 KB Output is correct
24 Correct 404 ms 67864 KB Output is correct
25 Correct 405 ms 68032 KB Output is correct
26 Correct 141 ms 45372 KB Output is correct
27 Correct 133 ms 45416 KB Output is correct
28 Correct 132 ms 45196 KB Output is correct
29 Correct 138 ms 45412 KB Output is correct
30 Correct 138 ms 45632 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 1 ms 344 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 344 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 344 KB Output is correct
38 Correct 1 ms 600 KB Output is correct
39 Correct 1 ms 344 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 169 ms 48588 KB Output is correct
42 Correct 316 ms 66028 KB Output is correct
43 Correct 340 ms 66240 KB Output is correct
44 Correct 110 ms 46416 KB Output is correct
45 Correct 344 ms 66240 KB Output is correct
46 Correct 324 ms 65984 KB Output is correct
47 Correct 328 ms 65984 KB Output is correct
48 Correct 322 ms 66192 KB Output is correct
49 Correct 320 ms 65904 KB Output is correct
50 Correct 330 ms 65984 KB Output is correct
51 Correct 333 ms 66244 KB Output is correct
52 Correct 321 ms 65920 KB Output is correct
53 Correct 347 ms 66348 KB Output is correct
54 Correct 336 ms 65988 KB Output is correct
55 Correct 333 ms 67008 KB Output is correct
56 Correct 361 ms 66432 KB Output is correct
57 Correct 324 ms 65984 KB Output is correct
58 Correct 321 ms 65984 KB Output is correct
59 Correct 120 ms 48980 KB Output is correct
60 Correct 317 ms 65900 KB Output is correct
61 Correct 329 ms 66224 KB Output is correct
62 Correct 98 ms 43844 KB Output is correct
63 Correct 107 ms 43088 KB Output is correct
64 Correct 96 ms 43840 KB Output is correct
65 Correct 93 ms 43844 KB Output is correct
66 Correct 125 ms 44236 KB Output is correct
67 Correct 110 ms 48720 KB Output is correct
68 Correct 97 ms 43952 KB Output is correct
69 Correct 124 ms 47452 KB Output is correct
70 Correct 97 ms 43844 KB Output is correct
71 Correct 112 ms 47396 KB Output is correct
72 Correct 220 ms 50252 KB Output is correct
73 Correct 417 ms 67788 KB Output is correct
74 Correct 381 ms 68016 KB Output is correct
75 Correct 388 ms 67524 KB Output is correct
76 Correct 372 ms 67528 KB Output is correct
77 Correct 367 ms 67784 KB Output is correct
78 Correct 367 ms 67568 KB Output is correct
79 Correct 370 ms 67712 KB Output is correct
80 Correct 390 ms 67776 KB Output is correct
81 Correct 381 ms 67856 KB Output is correct
82 Correct 406 ms 67520 KB Output is correct
83 Correct 390 ms 67616 KB Output is correct
84 Correct 420 ms 67736 KB Output is correct
85 Correct 456 ms 69308 KB Output is correct
86 Correct 446 ms 67656 KB Output is correct
87 Correct 403 ms 67632 KB Output is correct
88 Correct 413 ms 67584 KB Output is correct
89 Correct 230 ms 49708 KB Output is correct
90 Correct 396 ms 67712 KB Output is correct
91 Correct 405 ms 67268 KB Output is correct
92 Correct 164 ms 45372 KB Output is correct
93 Correct 184 ms 45284 KB Output is correct
94 Correct 144 ms 45380 KB Output is correct
95 Correct 168 ms 45420 KB Output is correct
96 Correct 203 ms 45008 KB Output is correct
97 Correct 214 ms 48288 KB Output is correct
98 Correct 162 ms 45264 KB Output is correct
99 Correct 227 ms 50252 KB Output is correct
100 Correct 161 ms 45380 KB Output is correct