oj.uz

답안 #918301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918301 2024-01-29T14:54:10 Z Whisper Evacuation plan (IZhO18_plan) C++17
100 / 100
 651 ms 188164 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using T = tuple<ll, ll, ll>;

#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 5e5 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int N, M, K, Q;
vector<pii> adj[MAX];
int g[MAX];
int f[MAX];

struct Dsu{
    int n;
    vector<int> par, sz;
    Dsu(int _n){
        this -> n = _n;
        par.resize(n + 5);
        sz.resize(n + 5, 1);
        iota(par.begin(), par.end(), 0ll);
    }
    int Find(int u){
        return u == par[u] ? u : par[u] = Find(par[u]);
    }
    bool unite(int u, int v){
        u = Find(u), v = Find(v);
        if (u == v) return 0;
        if (sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
        return 1;
    }
};

struct Data{
    int u, v, w;
    bool operator < (const Data& oth) const{
        return w > oth.w;
    }
};


int up[MAX][21], dep[MAX], mn[MAX][21];
void dfs(int u, int p){
    for (auto&[v, w] : adj[u]) if(v ^ p){
        up[v][0] = u;
        mn[v][0] = w;
        dep[v] = dep[u] + 1;
        for (int i = 1; i <= 20; ++i){
            up[v][i] = up[up[v][i - 1]][i - 1];
            mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
        }
        dfs(v, u);
    }
}

int query(int u, int v){
    int ans = INF;
    if (dep[u] < dep[v]) swap(u, v);
    int dis = dep[u] - dep[v];
    for (int i = 0; MASK(i) <= dis; ++i){
        if (BIT(dis, i)) minimize(ans, mn[u][i]), u = up[u][i];
    }
    if (u == v) return ans;
    int k = Lg(dep[v]);
    for (int i = k; i >= 0; --i) if(up[u][i] != up[v][i]){
        minimize(ans, mn[u][i]);
        minimize(ans, mn[v][i]);
        u = up[u][i], v = up[v][i];
    }
    minimize(ans, mn[u][0]); minimize(ans, mn[v][0]);
    return ans;
}
void Whisper(){
    cin >> N >> M;
    for (int i = 1; i <= M; ++i){
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cin >> K;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= K; ++i){
        cin >> g[i];
        q.push({0, g[i]});
        f[g[i]] = 0;
    }
    vector<int> vis(N + 1);
    while (!q.empty()){
        auto[du, u] = q.top(); q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (auto&[v, w] : adj[u]){
            if (minimize(f[v], f[u] + w)){
                q.push({f[v], v});
            }
        }
    }

    vector<int> ord(N + 1);
    iota(ord.begin(), ord.end(), 0);
    vector<Data> ed;
    for (int i = 1; i <= N; ++i){
        int u = ord[i];
        for (auto&[v, w] : adj[u]){
            int weight = min(f[u], f[v]);
            ed.push_back({u, v, weight});
        }
    }
    sort(all(ed));
    FOR(i, 0, N) adj[i].clear();
    Dsu dsu(N);
    for (auto&[u, v, w] : ed){
        if (dsu.unite(u, v)){
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }
    }
    memset(mn, 0x3f, sizeof mn);
    dfs(1, 0);
    cin >> Q;
    for (int i = 1; i <= Q; ++i){
        int u, v; cin >> u >> v;
        cout << query(u, v) << '\n';
    }

}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Compilation message

plan.cpp: In function 'void Whisper()':
plan.cpp:137:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  137 |         if (vis[u]) continue; vis[u] = 1;
      |         ^~
plan.cpp:137:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  137 |         if (vis[u]) continue; vis[u] = 1;
      |                               ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 104028 KB Output is correct
2 Correct 20 ms 104284 KB Output is correct
3 Correct 21 ms 104536 KB Output is correct
4 Correct 19 ms 104028 KB Output is correct
5 Correct 21 ms 104408 KB Output is correct
6 Correct 20 ms 104280 KB Output is correct
7 Correct 19 ms 104028 KB Output is correct
8 Correct 19 ms 104184 KB Output is correct
9 Correct 20 ms 104308 KB Output is correct
10 Correct 20 ms 104272 KB Output is correct
11 Correct 20 ms 104380 KB Output is correct
12 Correct 21 ms 104280 KB Output is correct
13 Correct 21 ms 104276 KB Output is correct
14 Correct 21 ms 104280 KB Output is correct
15 Correct 20 ms 104284 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 104028 KB Output is correct
2 Correct 20 ms 104284 KB Output is correct
3 Correct 21 ms 104536 KB Output is correct
4 Correct 19 ms 104028 KB Output is correct
5 Correct 21 ms 104408 KB Output is correct
6 Correct 20 ms 104280 KB Output is correct
7 Correct 19 ms 104028 KB Output is correct
8 Correct 19 ms 104184 KB Output is correct
9 Correct 20 ms 104308 KB Output is correct
10 Correct 20 ms 104272 KB Output is correct
11 Correct 20 ms 104380 KB Output is correct
12 Correct 21 ms 104280 KB Output is correct
13 Correct 21 ms 104276 KB Output is correct
14 Correct 21 ms 104280 KB Output is correct
15 Correct 20 ms 104284 KB Output is correct
16 Correct 167 ms 135988 KB Output is correct
17 Correct 460 ms 186916 KB Output is correct
18 Correct 48 ms 113612 KB Output is correct
19 Correct 147 ms 138572 KB Output is correct
20 Correct 502 ms 185324 KB Output is correct
21 Correct 301 ms 153456 KB Output is correct
22 Correct 272 ms 144512 KB Output is correct
23 Correct 536 ms 185112 KB Output is correct
24 Correct 560 ms 185216 KB Output is correct
25 Correct 620 ms 186908 KB Output is correct
26 Correct 177 ms 139076 KB Output is correct
27 Correct 186 ms 138084 KB Output is correct
28 Correct 182 ms 139040 KB Output is correct
29 Correct 187 ms 139056 KB Output is correct
30 Correct 178 ms 138248 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 104092 KB Output is correct
2 Correct 20 ms 104076 KB Output is correct
3 Correct 19 ms 104168 KB Output is correct
4 Correct 19 ms 104028 KB Output is correct
5 Correct 20 ms 104028 KB Output is correct
6 Correct 20 ms 104140 KB Output is correct
7 Correct 20 ms 104128 KB Output is correct
8 Correct 19 ms 104028 KB Output is correct
9 Correct 19 ms 104024 KB Output is correct
10 Correct 20 ms 104080 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 244 ms 146712 KB Output is correct
2 Correct 478 ms 176056 KB Output is correct
3 Correct 466 ms 175792 KB Output is correct
4 Correct 158 ms 137148 KB Output is correct
5 Correct 446 ms 175584 KB Output is correct
6 Correct 466 ms 175456 KB Output is correct
7 Correct 413 ms 183464 KB Output is correct
8 Correct 476 ms 185576 KB Output is correct
9 Correct 439 ms 184412 KB Output is correct
10 Correct 460 ms 184396 KB Output is correct
11 Correct 445 ms 184556 KB Output is correct
12 Correct 496 ms 185204 KB Output is correct
13 Correct 462 ms 185516 KB Output is correct
14 Correct 478 ms 183836 KB Output is correct
15 Correct 405 ms 186032 KB Output is correct
16 Correct 487 ms 185760 KB Output is correct
17 Correct 431 ms 185512 KB Output is correct
18 Correct 450 ms 183472 KB Output is correct
19 Correct 178 ms 141240 KB Output is correct
20 Correct 403 ms 185540 KB Output is correct
21 Correct 475 ms 185784 KB Output is correct
22 Correct 113 ms 137768 KB Output is correct
23 Correct 148 ms 136804 KB Output is correct
24 Correct 120 ms 136524 KB Output is correct
25 Correct 117 ms 136736 KB Output is correct
26 Correct 141 ms 136256 KB Output is correct
27 Correct 174 ms 141752 KB Output is correct
28 Correct 119 ms 137912 KB Output is correct
29 Correct 141 ms 140152 KB Output is correct
30 Correct 144 ms 137760 KB Output is correct
31 Correct 161 ms 140724 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 104028 KB Output is correct
2 Correct 20 ms 104284 KB Output is correct
3 Correct 21 ms 104536 KB Output is correct
4 Correct 19 ms 104028 KB Output is correct
5 Correct 21 ms 104408 KB Output is correct
6 Correct 20 ms 104280 KB Output is correct
7 Correct 19 ms 104028 KB Output is correct
8 Correct 19 ms 104184 KB Output is correct
9 Correct 20 ms 104308 KB Output is correct
10 Correct 20 ms 104272 KB Output is correct
11 Correct 20 ms 104380 KB Output is correct
12 Correct 21 ms 104280 KB Output is correct
13 Correct 21 ms 104276 KB Output is correct
14 Correct 21 ms 104280 KB Output is correct
15 Correct 20 ms 104284 KB Output is correct
16 Correct 167 ms 135988 KB Output is correct
17 Correct 460 ms 186916 KB Output is correct
18 Correct 48 ms 113612 KB Output is correct
19 Correct 147 ms 138572 KB Output is correct
20 Correct 502 ms 185324 KB Output is correct
21 Correct 301 ms 153456 KB Output is correct
22 Correct 272 ms 144512 KB Output is correct
23 Correct 536 ms 185112 KB Output is correct
24 Correct 560 ms 185216 KB Output is correct
25 Correct 620 ms 186908 KB Output is correct
26 Correct 177 ms 139076 KB Output is correct
27 Correct 186 ms 138084 KB Output is correct
28 Correct 182 ms 139040 KB Output is correct
29 Correct 187 ms 139056 KB Output is correct
30 Correct 178 ms 138248 KB Output is correct
31 Correct 19 ms 104092 KB Output is correct
32 Correct 20 ms 104076 KB Output is correct
33 Correct 19 ms 104168 KB Output is correct
34 Correct 19 ms 104028 KB Output is correct
35 Correct 20 ms 104028 KB Output is correct
36 Correct 20 ms 104140 KB Output is correct
37 Correct 20 ms 104128 KB Output is correct
38 Correct 19 ms 104028 KB Output is correct
39 Correct 19 ms 104024 KB Output is correct
40 Correct 20 ms 104080 KB Output is correct
41 Correct 244 ms 146712 KB Output is correct
42 Correct 478 ms 176056 KB Output is correct
43 Correct 466 ms 175792 KB Output is correct
44 Correct 158 ms 137148 KB Output is correct
45 Correct 446 ms 175584 KB Output is correct
46 Correct 466 ms 175456 KB Output is correct
47 Correct 413 ms 183464 KB Output is correct
48 Correct 476 ms 185576 KB Output is correct
49 Correct 439 ms 184412 KB Output is correct
50 Correct 460 ms 184396 KB Output is correct
51 Correct 445 ms 184556 KB Output is correct
52 Correct 496 ms 185204 KB Output is correct
53 Correct 462 ms 185516 KB Output is correct
54 Correct 478 ms 183836 KB Output is correct
55 Correct 405 ms 186032 KB Output is correct
56 Correct 487 ms 185760 KB Output is correct
57 Correct 431 ms 185512 KB Output is correct
58 Correct 450 ms 183472 KB Output is correct
59 Correct 178 ms 141240 KB Output is correct
60 Correct 403 ms 185540 KB Output is correct
61 Correct 475 ms 185784 KB Output is correct
62 Correct 113 ms 137768 KB Output is correct
63 Correct 148 ms 136804 KB Output is correct
64 Correct 120 ms 136524 KB Output is correct
65 Correct 117 ms 136736 KB Output is correct
66 Correct 141 ms 136256 KB Output is correct
67 Correct 174 ms 141752 KB Output is correct
68 Correct 119 ms 137912 KB Output is correct
69 Correct 141 ms 140152 KB Output is correct
70 Correct 144 ms 137760 KB Output is correct
71 Correct 161 ms 140724 KB Output is correct
72 Correct 303 ms 151684 KB Output is correct
73 Correct 566 ms 186324 KB Output is correct
74 Correct 529 ms 186056 KB Output is correct
75 Correct 519 ms 185456 KB Output is correct
76 Correct 463 ms 187280 KB Output is correct
77 Correct 472 ms 187008 KB Output is correct
78 Correct 504 ms 186960 KB Output is correct
79 Correct 485 ms 185740 KB Output is correct
80 Correct 588 ms 187532 KB Output is correct
81 Correct 526 ms 187564 KB Output is correct
82 Correct 543 ms 186016 KB Output is correct
83 Correct 589 ms 185852 KB Output is correct
84 Correct 637 ms 187984 KB Output is correct
85 Correct 603 ms 188164 KB Output is correct
86 Correct 651 ms 186144 KB Output is correct
87 Correct 581 ms 185160 KB Output is correct
88 Correct 641 ms 187568 KB Output is correct
89 Correct 292 ms 143220 KB Output is correct
90 Correct 560 ms 185408 KB Output is correct
91 Correct 480 ms 186820 KB Output is correct
92 Correct 161 ms 138696 KB Output is correct
93 Correct 247 ms 138676 KB Output is correct
94 Correct 166 ms 137972 KB Output is correct
95 Correct 186 ms 138808 KB Output is correct
96 Correct 232 ms 138960 KB Output is correct
97 Correct 302 ms 142184 KB Output is correct
98 Correct 208 ms 137912 KB Output is correct
99 Correct 338 ms 143080 KB Output is correct
100 Correct 199 ms 139316 KB Output is correct