oj.uz

답안 #85336

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85336 2018-11-19T11:25:31 Z mra2322001 Evacuation plan (IZhO18_plan) C++14
100 / 100
 1914 ms 49352 KB 
#include <bits/stdc++.h>
#define f0(i, n) for(int i(0); i < (n); i++)
#define f1(i, n) for(int i(1); i <= n; i++)

using namespace std;
typedef long long ll;
const int N = 100002;

int n, m, dist[N], parent[N];
pair <int, pair <int, int> > ed[N*5];
vector <vector <int> > v;
vector <vector <pair <int, int> > > a;

struct data{
    int u, v, l, r, ans;
} Q[N];

void dijkstra(){
    priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > q;
    f1(i, n) if(dist[i]==0) q.push({0, i});
    while(q.size()){
        int u = q.top().second, du = q.top().first;
        q.pop();
        if(du != dist[u]) continue;
        for(auto x:a[u]){
            if(dist[x.first] > du + x.second){
                dist[x.first] = du + x.second;
                q.push({dist[x.first], x.first});
            }
        }
    }
}

bool cmp(pair <int, pair <int, int> > a1, pair <int, pair <int, int> > a2){
    int x1 = min(dist[a1.second.first], dist[a1.second.second]);
    int x2 = min(dist[a2.second.first], dist[a2.second.second]);
    return x1 > x2;
}

int getroot(int u){
    if(parent[u]==u) return u;
    if(parent[u]==0) return u;
    parent[u] = getroot(parent[u]);
    return parent[u];
}

int Merge(int u, int v){
    parent[getroot(v)] = getroot(u);
}

int main(){
    ios_base::sync_with_stdio(0);

    cin >> n >> m;
    a.resize(n + 1);
    f1(i, m){
        int u, v, w; cin >> u >> v >> w;
        a[u].emplace_back(v, w);
        a[v].emplace_back(u, w);
        ed[i] = {w, {u, v}};
    }
    int len; cin >> len;
    memset(dist, 0x3f3f3f, sizeof(dist));
    while(len--){
        int x; cin >> x;
        dist[x] = 0;
    }
    dijkstra();
    sort(ed + 1, ed + m + 1, cmp);
    int q; cin >> q;
    f1(i, q){
        int u, v; cin >> u >> v;
        Q[i] = {u, v, 1, m, 0};
    }
    bool ok = 1;
    v.resize(m + 1);
    while(ok){
        f1(i, m) v[i].clear();
        ok = 0;
        f1(i, q){
            if(Q[i].l <= Q[i].r){
                int mid = (Q[i].l + Q[i].r)/2;
                v[mid].emplace_back(i);
                ok = 1;
            }
        }
        f1(i, n) parent[i] = 0;
        f1(i, m){
            Merge(ed[i].second.first, ed[i].second.second);
            for(auto x:v[i]){
                if(getroot(Q[x].u)==getroot(Q[x].v)){
                    Q[x].ans = i;
                    Q[x].r = i - 1;
                }
                else{
                    Q[x].l = i + 1;
                }
            }
        }
    }
    f1(i, q) cout << min(dist[ed[Q[i].ans].second.first], dist[ed[Q[i].ans].second.second]) << endl;
}

Compilation message

plan.cpp: In function 'int Merge(int, int)':
plan.cpp:49:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 6 ms 888 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 6 ms 888 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 6 ms 888 KB Output is correct
10 Correct 6 ms 888 KB Output is correct
11 Correct 7 ms 888 KB Output is correct
12 Correct 6 ms 888 KB Output is correct
13 Correct 6 ms 888 KB Output is correct
14 Correct 7 ms 888 KB Output is correct
15 Correct 6 ms 888 KB Output is correct
16 Correct 656 ms 22328 KB Output is correct
17 Correct 1779 ms 48448 KB Output is correct
18 Correct 113 ms 5196 KB Output is correct
19 Correct 521 ms 23384 KB Output is correct
20 Correct 1789 ms 48500 KB Output is correct
21 Correct 1006 ms 29980 KB Output is correct
22 Correct 544 ms 23096 KB Output is correct
23 Correct 1805 ms 48464 KB Output is correct
24 Correct 1848 ms 48444 KB Output is correct
25 Correct 1781 ms 48448 KB Output is correct
26 Correct 533 ms 23240 KB Output is correct
27 Correct 529 ms 23316 KB Output is correct
28 Correct 529 ms 23388 KB Output is correct
29 Correct 526 ms 23328 KB Output is correct
30 Correct 523 ms 23496 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 497 ms 17092 KB Output is correct
2 Correct 1201 ms 35272 KB Output is correct
3 Correct 1201 ms 35348 KB Output is correct
4 Correct 143 ms 11000 KB Output is correct
5 Correct 1248 ms 35184 KB Output is correct
6 Correct 1214 ms 35424 KB Output is correct
7 Correct 1202 ms 35284 KB Output is correct
8 Correct 1206 ms 35308 KB Output is correct
9 Correct 1187 ms 35220 KB Output is correct
10 Correct 1199 ms 35272 KB Output is correct
11 Correct 1200 ms 35376 KB Output is correct
12 Correct 1219 ms 35284 KB Output is correct
13 Correct 1226 ms 35164 KB Output is correct
14 Correct 1224 ms 35404 KB Output is correct
15 Correct 1203 ms 35280 KB Output is correct
16 Correct 1198 ms 35308 KB Output is correct
17 Correct 1196 ms 35336 KB Output is correct
18 Correct 1180 ms 35220 KB Output is correct
19 Correct 99 ms 10104 KB Output is correct
20 Correct 1195 ms 35284 KB Output is correct
21 Correct 1091 ms 35332 KB Output is correct
22 Correct 116 ms 11064 KB Output is correct
23 Correct 119 ms 10616 KB Output is correct
24 Correct 114 ms 11076 KB Output is correct
25 Correct 114 ms 11096 KB Output is correct
26 Correct 128 ms 10808 KB Output is correct
27 Correct 142 ms 10912 KB Output is correct
28 Correct 110 ms 11100 KB Output is correct
29 Correct 143 ms 11040 KB Output is correct
30 Correct 111 ms 11092 KB Output is correct
31 Correct 146 ms 10936 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 6 ms 888 KB Output is correct
3 Correct 6 ms 888 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 6 ms 888 KB Output is correct
6 Correct 6 ms 888 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 6 ms 888 KB Output is correct
10 Correct 6 ms 888 KB Output is correct
11 Correct 7 ms 888 KB Output is correct
12 Correct 6 ms 888 KB Output is correct
13 Correct 6 ms 888 KB Output is correct
14 Correct 7 ms 888 KB Output is correct
15 Correct 6 ms 888 KB Output is correct
16 Correct 656 ms 22328 KB Output is correct
17 Correct 1779 ms 48448 KB Output is correct
18 Correct 113 ms 5196 KB Output is correct
19 Correct 521 ms 23384 KB Output is correct
20 Correct 1789 ms 48500 KB Output is correct
21 Correct 1006 ms 29980 KB Output is correct
22 Correct 544 ms 23096 KB Output is correct
23 Correct 1805 ms 48464 KB Output is correct
24 Correct 1848 ms 48444 KB Output is correct
25 Correct 1781 ms 48448 KB Output is correct
26 Correct 533 ms 23240 KB Output is correct
27 Correct 529 ms 23316 KB Output is correct
28 Correct 529 ms 23388 KB Output is correct
29 Correct 526 ms 23328 KB Output is correct
30 Correct 523 ms 23496 KB Output is correct
31 Correct 3 ms 760 KB Output is correct
32 Correct 3 ms 760 KB Output is correct
33 Correct 3 ms 760 KB Output is correct
34 Correct 3 ms 788 KB Output is correct
35 Correct 3 ms 760 KB Output is correct
36 Correct 3 ms 760 KB Output is correct
37 Correct 2 ms 760 KB Output is correct
38 Correct 3 ms 760 KB Output is correct
39 Correct 2 ms 760 KB Output is correct
40 Correct 2 ms 760 KB Output is correct
41 Correct 497 ms 17092 KB Output is correct
42 Correct 1201 ms 35272 KB Output is correct
43 Correct 1201 ms 35348 KB Output is correct
44 Correct 143 ms 11000 KB Output is correct
45 Correct 1248 ms 35184 KB Output is correct
46 Correct 1214 ms 35424 KB Output is correct
47 Correct 1202 ms 35284 KB Output is correct
48 Correct 1206 ms 35308 KB Output is correct
49 Correct 1187 ms 35220 KB Output is correct
50 Correct 1199 ms 35272 KB Output is correct
51 Correct 1200 ms 35376 KB Output is correct
52 Correct 1219 ms 35284 KB Output is correct
53 Correct 1226 ms 35164 KB Output is correct
54 Correct 1224 ms 35404 KB Output is correct
55 Correct 1203 ms 35280 KB Output is correct
56 Correct 1198 ms 35308 KB Output is correct
57 Correct 1196 ms 35336 KB Output is correct
58 Correct 1180 ms 35220 KB Output is correct
59 Correct 99 ms 10104 KB Output is correct
60 Correct 1195 ms 35284 KB Output is correct
61 Correct 1091 ms 35332 KB Output is correct
62 Correct 116 ms 11064 KB Output is correct
63 Correct 119 ms 10616 KB Output is correct
64 Correct 114 ms 11076 KB Output is correct
65 Correct 114 ms 11096 KB Output is correct
66 Correct 128 ms 10808 KB Output is correct
67 Correct 142 ms 10912 KB Output is correct
68 Correct 110 ms 11100 KB Output is correct
69 Correct 143 ms 11040 KB Output is correct
70 Correct 111 ms 11092 KB Output is correct
71 Correct 146 ms 10936 KB Output is correct
72 Correct 1065 ms 30100 KB Output is correct
73 Correct 1810 ms 49172 KB Output is correct
74 Correct 1812 ms 49028 KB Output is correct
75 Correct 1864 ms 49352 KB Output is correct
76 Correct 1878 ms 49036 KB Output is correct
77 Correct 1876 ms 49088 KB Output is correct
78 Correct 1855 ms 49204 KB Output is correct
79 Correct 1914 ms 49124 KB Output is correct
80 Correct 1872 ms 48936 KB Output is correct
81 Correct 1805 ms 49304 KB Output is correct
82 Correct 1798 ms 48940 KB Output is correct
83 Correct 1819 ms 49200 KB Output is correct
84 Correct 1812 ms 49304 KB Output is correct
85 Correct 1830 ms 49292 KB Output is correct
86 Correct 1794 ms 49164 KB Output is correct
87 Correct 1804 ms 48896 KB Output is correct
88 Correct 1846 ms 49128 KB Output is correct
89 Correct 539 ms 23732 KB Output is correct
90 Correct 1829 ms 49088 KB Output is correct
91 Correct 1629 ms 48320 KB Output is correct
92 Correct 555 ms 23788 KB Output is correct
93 Correct 573 ms 22172 KB Output is correct
94 Correct 550 ms 23648 KB Output is correct
95 Correct 543 ms 23776 KB Output is correct
96 Correct 548 ms 20880 KB Output is correct
97 Correct 569 ms 22656 KB Output is correct
98 Correct 536 ms 23616 KB Output is correct
99 Correct 571 ms 22640 KB Output is correct
100 Correct 540 ms 23656 KB Output is correct