oj.uz

답안 #90911

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90911 2018-12-25T07:25:49 Z toloraia Evacuation plan (IZhO18_plan) C++17
100 / 100
 3823 ms 45816 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N = 5e5 + 5, INF = 1e9 + 5;

int n, m;
vector < int > g[N], gg[N];
int mas[N];
priority_queue < pair < int, int > > Q;
int q;
int s[N], f[N], l[N], r[N],  mid[N];
pair < int, int > P[N], PP[N];
bool F[N];
int p[N];
int parent (int x){
    if (p[x] == x)
        return x;
    return p[x] = parent (p[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    while (m--){
        int u, v, x;
        cin>>u>>v>>x;
        g[u].pb (v);
        gg[u].pb (x);
        g[v].pb (u);
        gg[v].pb (x);
    }
    for (int i = 1; i <= n; i++)
        mas[i] = INF;
    cin>>m;
    while (m--){
        int x;
        cin>>x;
        mas[x] = 0;
        Q.push ({-mas[x], x});
    }
    cin>>q;
    for (int i = 1; i <= q; i++){
        cin>>s[i]>>f[i];
        l[i] = 1;
        r[i] = n;
    }
    while (Q.size() > 0){
        int k = Q.top().S;
        Q.pop();
        if (F[k])
            continue;
        F[k] = 1;
        for (int i = 0; i < g[k].size(); i++){
            int to = g[k][i];
            if (mas[to] > mas[k] + gg[k][i]){
                mas[to] = mas[k] + gg[k][i];
                Q.push ({-mas[to], to});
            }
        }
    }
    for (int i = 1; i <= n; i++)
        P[i] = {-mas[i], i};
    sort (P + 1, P + n + 1);
    for (int mtvleli = 0; mtvleli < 30; mtvleli++){
        for (int i = 1; i <= q; i++){
            mid[i] = (l[i] + r[i]) / 2;
            PP[i] = {mid[i], i};
        }
        sort (PP + 1, PP + q + 1);
        int I = 1;
        for (int i = 1; i <= n; i++){
            F[i] = 0;
            p[i] = i;
        }
        for (int i = 1; i <= n; i++){
            int u = P[i].S;
            F[u] = 1;
            for (int j = 0; j < g[u].size(); j++)
                if (F[g[u][j]] == 1){
                    parent (g[u][j]);
                    p[p[g[u][j]]] = u;
                }
            for (; I <= q && PP[I].F == i; I++){
                int k = PP[I].S;
                int u = s[k], v = f[k];
                parent(u);
                parent(v);
                if (p[u] == p[v])
                    r[k] = mid[k];
                else
                    l[k] = mid[k] + 1;
            }
        }
    }
    for (int i = 1; i <= q; i++)
        cout<<-P[l[i]].F<<endl;
    return 0;
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:59:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[k].size(); i++){
                         ~~^~~~~~~~~~~~~
plan.cpp:84:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[u].size(); j++)
                             ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 29 ms 24056 KB Output is correct
3 Correct 29 ms 24056 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 29 ms 24056 KB Output is correct
6 Correct 29 ms 24056 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 31 ms 23964 KB Output is correct
10 Correct 32 ms 24028 KB Output is correct
11 Correct 31 ms 24100 KB Output is correct
12 Correct 29 ms 24056 KB Output is correct
13 Correct 31 ms 24056 KB Output is correct
14 Correct 31 ms 24056 KB Output is correct
15 Correct 31 ms 23944 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 29 ms 24056 KB Output is correct
3 Correct 29 ms 24056 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 29 ms 24056 KB Output is correct
6 Correct 29 ms 24056 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 31 ms 23964 KB Output is correct
10 Correct 32 ms 24028 KB Output is correct
11 Correct 31 ms 24100 KB Output is correct
12 Correct 29 ms 24056 KB Output is correct
13 Correct 31 ms 24056 KB Output is correct
14 Correct 31 ms 24056 KB Output is correct
15 Correct 31 ms 23944 KB Output is correct
16 Correct 1416 ms 34228 KB Output is correct
17 Correct 3707 ms 45752 KB Output is correct
18 Correct 217 ms 26160 KB Output is correct
19 Correct 838 ms 36704 KB Output is correct
20 Correct 3700 ms 45604 KB Output is correct
21 Correct 2021 ms 37832 KB Output is correct
22 Correct 1072 ms 35696 KB Output is correct
23 Correct 3645 ms 45476 KB Output is correct
24 Correct 3665 ms 45520 KB Output is correct
25 Correct 3616 ms 45488 KB Output is correct
26 Correct 886 ms 36512 KB Output is correct
27 Correct 879 ms 36700 KB Output is correct
28 Correct 916 ms 36536 KB Output is correct
29 Correct 874 ms 36628 KB Output is correct
30 Correct 781 ms 36816 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 29 ms 23828 KB Output is correct
3 Correct 31 ms 23932 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23836 KB Output is correct
6 Correct 24 ms 23836 KB Output is correct
7 Correct 29 ms 23928 KB Output is correct
8 Correct 29 ms 23928 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 24 ms 23928 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1384 ms 34872 KB Output is correct
2 Correct 2829 ms 42472 KB Output is correct
3 Correct 2870 ms 42444 KB Output is correct
4 Correct 567 ms 32568 KB Output is correct
5 Correct 2807 ms 42428 KB Output is correct
6 Correct 2833 ms 42444 KB Output is correct
7 Correct 2828 ms 42436 KB Output is correct
8 Correct 2829 ms 42444 KB Output is correct
9 Correct 2808 ms 42460 KB Output is correct
10 Correct 2807 ms 42440 KB Output is correct
11 Correct 2816 ms 42468 KB Output is correct
12 Correct 2786 ms 42460 KB Output is correct
13 Correct 2861 ms 42500 KB Output is correct
14 Correct 2805 ms 42476 KB Output is correct
15 Correct 2835 ms 42488 KB Output is correct
16 Correct 2861 ms 42468 KB Output is correct
17 Correct 2806 ms 42456 KB Output is correct
18 Correct 2823 ms 42432 KB Output is correct
19 Correct 331 ms 32648 KB Output is correct
20 Correct 2771 ms 42428 KB Output is correct
21 Correct 2359 ms 42208 KB Output is correct
22 Correct 279 ms 33576 KB Output is correct
23 Correct 376 ms 32080 KB Output is correct
24 Correct 306 ms 33576 KB Output is correct
25 Correct 286 ms 33480 KB Output is correct
26 Correct 465 ms 32288 KB Output is correct
27 Correct 582 ms 32648 KB Output is correct
28 Correct 286 ms 33580 KB Output is correct
29 Correct 557 ms 32576 KB Output is correct
30 Correct 275 ms 33636 KB Output is correct
31 Correct 608 ms 32716 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 29 ms 24056 KB Output is correct
3 Correct 29 ms 24056 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 29 ms 24056 KB Output is correct
6 Correct 29 ms 24056 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 31 ms 23964 KB Output is correct
10 Correct 32 ms 24028 KB Output is correct
11 Correct 31 ms 24100 KB Output is correct
12 Correct 29 ms 24056 KB Output is correct
13 Correct 31 ms 24056 KB Output is correct
14 Correct 31 ms 24056 KB Output is correct
15 Correct 31 ms 23944 KB Output is correct
16 Correct 1416 ms 34228 KB Output is correct
17 Correct 3707 ms 45752 KB Output is correct
18 Correct 217 ms 26160 KB Output is correct
19 Correct 838 ms 36704 KB Output is correct
20 Correct 3700 ms 45604 KB Output is correct
21 Correct 2021 ms 37832 KB Output is correct
22 Correct 1072 ms 35696 KB Output is correct
23 Correct 3645 ms 45476 KB Output is correct
24 Correct 3665 ms 45520 KB Output is correct
25 Correct 3616 ms 45488 KB Output is correct
26 Correct 886 ms 36512 KB Output is correct
27 Correct 879 ms 36700 KB Output is correct
28 Correct 916 ms 36536 KB Output is correct
29 Correct 874 ms 36628 KB Output is correct
30 Correct 781 ms 36816 KB Output is correct
31 Correct 24 ms 23928 KB Output is correct
32 Correct 29 ms 23828 KB Output is correct
33 Correct 31 ms 23932 KB Output is correct
34 Correct 24 ms 23928 KB Output is correct
35 Correct 24 ms 23836 KB Output is correct
36 Correct 24 ms 23836 KB Output is correct
37 Correct 29 ms 23928 KB Output is correct
38 Correct 29 ms 23928 KB Output is correct
39 Correct 24 ms 23928 KB Output is correct
40 Correct 24 ms 23928 KB Output is correct
41 Correct 1384 ms 34872 KB Output is correct
42 Correct 2829 ms 42472 KB Output is correct
43 Correct 2870 ms 42444 KB Output is correct
44 Correct 567 ms 32568 KB Output is correct
45 Correct 2807 ms 42428 KB Output is correct
46 Correct 2833 ms 42444 KB Output is correct
47 Correct 2828 ms 42436 KB Output is correct
48 Correct 2829 ms 42444 KB Output is correct
49 Correct 2808 ms 42460 KB Output is correct
50 Correct 2807 ms 42440 KB Output is correct
51 Correct 2816 ms 42468 KB Output is correct
52 Correct 2786 ms 42460 KB Output is correct
53 Correct 2861 ms 42500 KB Output is correct
54 Correct 2805 ms 42476 KB Output is correct
55 Correct 2835 ms 42488 KB Output is correct
56 Correct 2861 ms 42468 KB Output is correct
57 Correct 2806 ms 42456 KB Output is correct
58 Correct 2823 ms 42432 KB Output is correct
59 Correct 331 ms 32648 KB Output is correct
60 Correct 2771 ms 42428 KB Output is correct
61 Correct 2359 ms 42208 KB Output is correct
62 Correct 279 ms 33576 KB Output is correct
63 Correct 376 ms 32080 KB Output is correct
64 Correct 306 ms 33576 KB Output is correct
65 Correct 286 ms 33480 KB Output is correct
66 Correct 465 ms 32288 KB Output is correct
67 Correct 582 ms 32648 KB Output is correct
68 Correct 286 ms 33580 KB Output is correct
69 Correct 557 ms 32576 KB Output is correct
70 Correct 275 ms 33636 KB Output is correct
71 Correct 608 ms 32716 KB Output is correct
72 Correct 2383 ms 38212 KB Output is correct
73 Correct 3724 ms 45552 KB Output is correct
74 Correct 3675 ms 45696 KB Output is correct
75 Correct 3779 ms 45560 KB Output is correct
76 Correct 3706 ms 45576 KB Output is correct
77 Correct 3793 ms 45580 KB Output is correct
78 Correct 3741 ms 45564 KB Output is correct
79 Correct 3823 ms 45628 KB Output is correct
80 Correct 3791 ms 45696 KB Output is correct
81 Correct 3762 ms 45684 KB Output is correct
82 Correct 3768 ms 45680 KB Output is correct
83 Correct 3738 ms 45816 KB Output is correct
84 Correct 3732 ms 45572 KB Output is correct
85 Correct 3681 ms 45512 KB Output is correct
86 Correct 3711 ms 45572 KB Output is correct
87 Correct 3703 ms 45704 KB Output is correct
88 Correct 3720 ms 45636 KB Output is correct
89 Correct 1414 ms 36300 KB Output is correct
90 Correct 3739 ms 45716 KB Output is correct
91 Correct 3211 ms 45152 KB Output is correct
92 Correct 841 ms 36628 KB Output is correct
93 Correct 1285 ms 35556 KB Output is correct
94 Correct 819 ms 36452 KB Output is correct
95 Correct 868 ms 36580 KB Output is correct
96 Correct 1178 ms 35280 KB Output is correct
97 Correct 1464 ms 35576 KB Output is correct
98 Correct 793 ms 36576 KB Output is correct
99 Correct 1431 ms 35460 KB Output is correct
100 Correct 928 ms 36588 KB Output is correct