oj.uz

Submission #981449

# Submission time Handle Problem Language Result Execution time Memory
981449 2024-05-13T08:27:23 Z vjudge1 Evacuation plan (IZhO18_plan) C++17
100 / 100
 415 ms 103628 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define lwb lower_bound
#define upb upper_bound

#define TASKNAME "NAME"

void init()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ///freopen(TASKNAME".INP","r",stdin); freopen(TASKNAME".OUT","w",stdout);
}

const int SZ = 1e6+5;
const ll INF = INT_MAX / 2, MOD = 1e9+7, INFLL = 2e18;
const double epsilon = 1e-3;

int n,m,k,q, d[SZ], a[SZ];

struct Node
{
    int u,d;

    bool operator < (const Node& other) const
    {
        return d > other.d;
    }
};
priority_queue<Node> pq;
vector<pii> adj[SZ];

void dijkstra()
{
    while(!pq.empty())
    {
        int u = pq.top().u, dist = pq.top().d;
        pq.pop();
        if(d[u] < dist) continue;
        for(pii e : adj[u])
        {
            int v = e.fi, w = e.se;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                pq.push({v, d[v]});
            }
        }
    }
}

bool cmp(int x, int y)
{
    return d[x] > d[y];
}

struct DSU
{
    int s[SZ], par[SZ];

    void init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            s[i] = 1;
            par[i] = i;
        }
    }

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

    void join(int u, int v)
    {
        if(s[u] < s[v]) swap(u, v);
        s[u] += s[v];
        par[v] = u;
    }
} dsu;

bool check[SZ];
vector<int> mst[SZ];
int h[SZ], up[SZ][20], val[SZ][20];

void dfs(int u, int pre)
{
    for(int v : mst[u])
    {
        if(v == pre) continue;
        h[v] = h[u] + 1;
        val[v][0] = d[u];
        up[v][0] = u;
        for(int i = 1; i < 20; i++)
        {
            up[v][i] = up[up[v][i-1]][i-1];
            val[v][i] = min(val[v][i-1], val[up[v][i-1]][i-1]);
        }
        dfs(v, u);
    }
}

int res(int u, int v)
{
    int mn = min(d[u], d[v]);
    if(h[u] != h[v])
    {
        if(h[u] < h[v]) swap(u, v);
        int diff = h[u] - h[v];
        for(int i = 0; i < 20; i++)
        {
            if(diff >> i & 1)
            {
                mn = min(mn, val[u][i]);
                u = up[u][i];
            }
        }
    }
    if(u == v) return mn;
    for(int i = 19; i >= 0; i--)
    {
        if(up[u][i] != up[v][i])
        {
            mn = min({mn, val[u][i], val[v][i]});
            u = up[u][i];
            v = up[v][i];
        }
    }
    return min(mn, d[up[u][0]]);
}

int main()
{
    init();
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    for(int i = 1; i <= n; i++)
    {
        d[i] = INF;
        a[i] = i;
    }
    cin >> k;
    for(int i = 1; i <= k; i++)
    {
        int u;
        cin >> u;
        pq.push({u, 0});
        d[u] = 0;
    }
    dijkstra();
    sort(a + 1, a + n + 1, cmp);
    dsu.init(n);
    for(int i = 1; i <= n; i++)
    {
        int u = a[i];
        check[u] = true;
        for(pii e : adj[u])
        {
            int v = e.fi, w = e.se;
            int x = dsu.get(u), y = dsu.get(v);
            if(!check[v] || x == y) continue;
            dsu.join(x, y);
            mst[u].pb(v);
            mst[v].pb(u);
        }
    }
    dfs(1, 0);
    cin >> q;
    while(q--)
    {
        int u,v;
        cin >> u >> v;
        cout << res(u, v) << '\n';
    }
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:175:27: warning: unused variable 'w' [-Wunused-variable]
  175 |             int v = e.fi, w = e.se;
      |                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 59932 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 14 ms 60252 KB Output is correct
4 Correct 14 ms 60252 KB Output is correct
5 Correct 13 ms 59996 KB Output is correct
6 Correct 13 ms 59972 KB Output is correct
7 Correct 13 ms 59996 KB Output is correct
8 Correct 14 ms 59996 KB Output is correct
9 Correct 14 ms 59972 KB Output is correct
10 Correct 15 ms 59996 KB Output is correct
11 Correct 13 ms 59992 KB Output is correct
12 Correct 13 ms 59992 KB Output is correct
13 Correct 13 ms 59992 KB Output is correct
14 Correct 13 ms 59996 KB Output is correct
15 Correct 13 ms 59992 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 59932 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 14 ms 60252 KB Output is correct
4 Correct 14 ms 60252 KB Output is correct
5 Correct 13 ms 59996 KB Output is correct
6 Correct 13 ms 59972 KB Output is correct
7 Correct 13 ms 59996 KB Output is correct
8 Correct 14 ms 59996 KB Output is correct
9 Correct 14 ms 59972 KB Output is correct
10 Correct 15 ms 59996 KB Output is correct
11 Correct 13 ms 59992 KB Output is correct
12 Correct 13 ms 59992 KB Output is correct
13 Correct 13 ms 59992 KB Output is correct
14 Correct 13 ms 59996 KB Output is correct
15 Correct 13 ms 59992 KB Output is correct
16 Correct 129 ms 83984 KB Output is correct
17 Correct 326 ms 103476 KB Output is correct
18 Correct 35 ms 64544 KB Output is correct
19 Correct 121 ms 88140 KB Output is correct
20 Correct 329 ms 103268 KB Output is correct
21 Correct 185 ms 91336 KB Output is correct
22 Correct 154 ms 94544 KB Output is correct
23 Correct 323 ms 103628 KB Output is correct
24 Correct 336 ms 103368 KB Output is correct
25 Correct 329 ms 103552 KB Output is correct
26 Correct 120 ms 88128 KB Output is correct
27 Correct 121 ms 88132 KB Output is correct
28 Correct 126 ms 88132 KB Output is correct
29 Correct 134 ms 88136 KB Output is correct
30 Correct 119 ms 88132 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 59740 KB Output is correct
2 Correct 13 ms 59740 KB Output is correct
3 Correct 12 ms 59744 KB Output is correct
4 Correct 13 ms 59996 KB Output is correct
5 Correct 13 ms 59740 KB Output is correct
6 Correct 13 ms 59960 KB Output is correct
7 Correct 13 ms 59740 KB Output is correct
8 Correct 13 ms 59740 KB Output is correct
9 Correct 12 ms 59740 KB Output is correct
10 Correct 12 ms 59740 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 89324 KB Output is correct
2 Correct 283 ms 101576 KB Output is correct
3 Correct 284 ms 101576 KB Output is correct
4 Correct 121 ms 89448 KB Output is correct
5 Correct 272 ms 101832 KB Output is correct
6 Correct 268 ms 101580 KB Output is correct
7 Correct 270 ms 101688 KB Output is correct
8 Correct 282 ms 101576 KB Output is correct
9 Correct 329 ms 101732 KB Output is correct
10 Correct 275 ms 101572 KB Output is correct
11 Correct 314 ms 101808 KB Output is correct
12 Correct 315 ms 101644 KB Output is correct
13 Correct 297 ms 101856 KB Output is correct
14 Correct 312 ms 101832 KB Output is correct
15 Correct 290 ms 101828 KB Output is correct
16 Correct 276 ms 101672 KB Output is correct
17 Correct 271 ms 101692 KB Output is correct
18 Correct 285 ms 101664 KB Output is correct
19 Correct 119 ms 92244 KB Output is correct
20 Correct 286 ms 101836 KB Output is correct
21 Correct 260 ms 101812 KB Output is correct
22 Correct 90 ms 86688 KB Output is correct
23 Correct 102 ms 86096 KB Output is correct
24 Correct 87 ms 86688 KB Output is correct
25 Correct 94 ms 86692 KB Output is correct
26 Correct 128 ms 86612 KB Output is correct
27 Correct 124 ms 91732 KB Output is correct
28 Correct 90 ms 86556 KB Output is correct
29 Correct 117 ms 90452 KB Output is correct
30 Correct 89 ms 86512 KB Output is correct
31 Correct 114 ms 90528 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 59932 KB Output is correct
2 Correct 13 ms 59996 KB Output is correct
3 Correct 14 ms 60252 KB Output is correct
4 Correct 14 ms 60252 KB Output is correct
5 Correct 13 ms 59996 KB Output is correct
6 Correct 13 ms 59972 KB Output is correct
7 Correct 13 ms 59996 KB Output is correct
8 Correct 14 ms 59996 KB Output is correct
9 Correct 14 ms 59972 KB Output is correct
10 Correct 15 ms 59996 KB Output is correct
11 Correct 13 ms 59992 KB Output is correct
12 Correct 13 ms 59992 KB Output is correct
13 Correct 13 ms 59992 KB Output is correct
14 Correct 13 ms 59996 KB Output is correct
15 Correct 13 ms 59992 KB Output is correct
16 Correct 129 ms 83984 KB Output is correct
17 Correct 326 ms 103476 KB Output is correct
18 Correct 35 ms 64544 KB Output is correct
19 Correct 121 ms 88140 KB Output is correct
20 Correct 329 ms 103268 KB Output is correct
21 Correct 185 ms 91336 KB Output is correct
22 Correct 154 ms 94544 KB Output is correct
23 Correct 323 ms 103628 KB Output is correct
24 Correct 336 ms 103368 KB Output is correct
25 Correct 329 ms 103552 KB Output is correct
26 Correct 120 ms 88128 KB Output is correct
27 Correct 121 ms 88132 KB Output is correct
28 Correct 126 ms 88132 KB Output is correct
29 Correct 134 ms 88136 KB Output is correct
30 Correct 119 ms 88132 KB Output is correct
31 Correct 12 ms 59740 KB Output is correct
32 Correct 13 ms 59740 KB Output is correct
33 Correct 12 ms 59744 KB Output is correct
34 Correct 13 ms 59996 KB Output is correct
35 Correct 13 ms 59740 KB Output is correct
36 Correct 13 ms 59960 KB Output is correct
37 Correct 13 ms 59740 KB Output is correct
38 Correct 13 ms 59740 KB Output is correct
39 Correct 12 ms 59740 KB Output is correct
40 Correct 12 ms 59740 KB Output is correct
41 Correct 179 ms 89324 KB Output is correct
42 Correct 283 ms 101576 KB Output is correct
43 Correct 284 ms 101576 KB Output is correct
44 Correct 121 ms 89448 KB Output is correct
45 Correct 272 ms 101832 KB Output is correct
46 Correct 268 ms 101580 KB Output is correct
47 Correct 270 ms 101688 KB Output is correct
48 Correct 282 ms 101576 KB Output is correct
49 Correct 329 ms 101732 KB Output is correct
50 Correct 275 ms 101572 KB Output is correct
51 Correct 314 ms 101808 KB Output is correct
52 Correct 315 ms 101644 KB Output is correct
53 Correct 297 ms 101856 KB Output is correct
54 Correct 312 ms 101832 KB Output is correct
55 Correct 290 ms 101828 KB Output is correct
56 Correct 276 ms 101672 KB Output is correct
57 Correct 271 ms 101692 KB Output is correct
58 Correct 285 ms 101664 KB Output is correct
59 Correct 119 ms 92244 KB Output is correct
60 Correct 286 ms 101836 KB Output is correct
61 Correct 260 ms 101812 KB Output is correct
62 Correct 90 ms 86688 KB Output is correct
63 Correct 102 ms 86096 KB Output is correct
64 Correct 87 ms 86688 KB Output is correct
65 Correct 94 ms 86692 KB Output is correct
66 Correct 128 ms 86612 KB Output is correct
67 Correct 124 ms 91732 KB Output is correct
68 Correct 90 ms 86556 KB Output is correct
69 Correct 117 ms 90452 KB Output is correct
70 Correct 89 ms 86512 KB Output is correct
71 Correct 114 ms 90528 KB Output is correct
72 Correct 197 ms 91340 KB Output is correct
73 Correct 329 ms 103100 KB Output is correct
74 Correct 415 ms 103420 KB Output is correct
75 Correct 326 ms 103336 KB Output is correct
76 Correct 329 ms 103224 KB Output is correct
77 Correct 358 ms 103476 KB Output is correct
78 Correct 331 ms 103320 KB Output is correct
79 Correct 346 ms 103476 KB Output is correct
80 Correct 347 ms 103364 KB Output is correct
81 Correct 340 ms 103360 KB Output is correct
82 Correct 349 ms 103432 KB Output is correct
83 Correct 354 ms 103372 KB Output is correct
84 Correct 330 ms 103376 KB Output is correct
85 Correct 340 ms 103508 KB Output is correct
86 Correct 331 ms 103372 KB Output is correct
87 Correct 338 ms 103436 KB Output is correct
88 Correct 328 ms 103268 KB Output is correct
89 Correct 205 ms 92752 KB Output is correct
90 Correct 342 ms 103372 KB Output is correct
91 Correct 322 ms 103424 KB Output is correct
92 Correct 114 ms 88392 KB Output is correct
93 Correct 166 ms 88148 KB Output is correct
94 Correct 120 ms 88136 KB Output is correct
95 Correct 115 ms 88136 KB Output is correct
96 Correct 164 ms 87636 KB Output is correct
97 Correct 191 ms 91472 KB Output is correct
98 Correct 112 ms 88136 KB Output is correct
99 Correct 192 ms 93520 KB Output is correct
100 Correct 115 ms 88132 KB Output is correct