답안 #54065 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54065	2018-07-02T09:35:14 Z	egorlifar	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2229 ms	32356 KB

plan

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <deque>
    
     
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228
#define prev prev228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
#define x first
#define y second
const string FILENAME = "input";
const int MAXN = 100228;

//11:50
//16:50
int n, m;
vector<pair<int, int> > g[MAXN];
int id[MAXN];
int dist[MAXN];
int s[MAXN], t[MAXN];
int l[MAXN], r[MAXN];
bool good[MAXN];
int parent[MAXN];
vector<int> need[MAXN];


int findset(int a) {
    if (a == parent[a]) {
        return a;
    }
    return parent[a] = findset(parent[a]);
}


void makeset(int a) {
    parent[a] = a;
}


void setunion(int a, int b) {
    a = findset(a);
    b = findset(b);
    if (a == b) {
        return;
    }
    parent[a] = b;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//read(FILENAME);
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--, b--;
        g[a].pb({b, c});
        g[b].pb({a, c});
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> id[i];
        id[i]--;
    }
    for (int i = 0; i < n; i++) {
        dist[i] = 1e9;
    }
    set<pair<int, int> > ss;
    for (int i = 0; i < k; i++) {
        dist[id[i]] = 0;
        ss.insert({0, id[i]});
    }
    //return 0;
    while (!ss.empty()) {
        pair<int, int> p = *ss.begin();
        ss.erase(p);
        int u = p.second;
        for (auto h: g[u]) {
            if (dist[h.first] > dist[u] + h.second) {
                ss.erase({dist[h.first], h.first});
                dist[h.first] = dist[u] + h.second;
                ss.insert({dist[h.first], h.first});
            }
        }
    }
  // return 0;
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> s[i] >> t[i]; 
        s[i]--, t[i]--;
    }
    vector<pair<int, int> > st;
    for (int i = 0; i < n; i++) {
        st.pb({dist[i], i});
    }
    sort(all(st));
    reverse(all(st));
    for (int i = 0; i < q; i++) {
        l[i] = 0;
        r[i] = n - 1;
    }
    while (true) {
        bool was = false;
        for (int i = 0; i < n; i++) {
            need[i].clear();
        }
        for (int i = 0; i < q; i++) {
            if (l[i] != r[i]) {
                int mid = (l[i] + r[i]) >> 1;;
                need[mid].pb(i);
                was = true;
            }
        }
        if (!was) {
            break;
        }
        for (int i = 0; i < n; i++) {
            makeset(i);
            good[i] = false;
        }
        for (int i = 0; i < n; i++) {
            good[st[i].second] = true;
            for (auto x: g[st[i].second]) {
                if (good[x.first]) {
                    setunion(x.first, st[i].second);
                }
            }
            for (auto x: need[i]) {
                if (findset(s[x]) != findset(t[x])) {
                    l[x] = i + 1;
                } else {
                    r[x] = i;
                }
            }
        }
    }
    for (int i = 0; i < q; i++) {
        cout << st[l[i]].first << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	7 ms	5240 KB	Output is correct
3	Correct	7 ms	5240 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	8 ms	5240 KB	Output is correct
6	Correct	8 ms	5240 KB	Output is correct
7	Correct	6 ms	5112 KB	Output is correct
8	Correct	6 ms	5112 KB	Output is correct
9	Correct	8 ms	5240 KB	Output is correct
10	Correct	8 ms	5240 KB	Output is correct
11	Correct	8 ms	5244 KB	Output is correct
12	Correct	7 ms	5240 KB	Output is correct
13	Correct	9 ms	5212 KB	Output is correct
14	Correct	8 ms	5316 KB	Output is correct
15	Correct	8 ms	5244 KB	Output is correct
16	Correct	663 ms	22092 KB	Output is correct
17	Correct	2229 ms	32256 KB	Output is correct
18	Correct	94 ms	7736 KB	Output is correct
19	Correct	289 ms	20660 KB	Output is correct
20	Correct	2066 ms	32324 KB	Output is correct
21	Correct	1004 ms	25324 KB	Output is correct
22	Correct	468 ms	23408 KB	Output is correct
23	Correct	2049 ms	32356 KB	Output is correct
24	Correct	2041 ms	32092 KB	Output is correct
25	Correct	2051 ms	32056 KB	Output is correct
26	Correct	293 ms	20264 KB	Output is correct
27	Correct	285 ms	20244 KB	Output is correct
28	Correct	304 ms	20392 KB	Output is correct
29	Correct	307 ms	20660 KB	Output is correct
30	Correct	278 ms	20564 KB	Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	921 ms	13680 KB	Output is correct
2	Correct	1759 ms	22296 KB	Output is correct
3	Correct	1816 ms	22136 KB	Output is correct
4	Correct	307 ms	10944 KB	Output is correct
5	Correct	1699 ms	22032 KB	Output is correct
6	Correct	1814 ms	22104 KB	Output is correct
7	Correct	1827 ms	22116 KB	Output is correct
8	Correct	1822 ms	21952 KB	Output is correct
9	Correct	1818 ms	22112 KB	Output is correct
10	Correct	1736 ms	22136 KB	Output is correct
11	Correct	1789 ms	21976 KB	Output is correct
12	Correct	1816 ms	21968 KB	Output is correct
13	Correct	1824 ms	21524 KB	Output is correct
14	Correct	1776 ms	21580 KB	Output is correct
15	Correct	1718 ms	21576 KB	Output is correct
16	Correct	1805 ms	21492 KB	Output is correct
17	Correct	1867 ms	21516 KB	Output is correct
18	Correct	1867 ms	21568 KB	Output is correct
19	Correct	240 ms	10776 KB	Output is correct
20	Correct	1834 ms	21640 KB	Output is correct
21	Correct	1365 ms	22560 KB	Output is correct
22	Correct	211 ms	14092 KB	Output is correct
23	Correct	226 ms	10556 KB	Output is correct
24	Correct	212 ms	14188 KB	Output is correct
25	Correct	208 ms	14188 KB	Output is correct
26	Correct	261 ms	10440 KB	Output is correct
27	Correct	288 ms	10728 KB	Output is correct
28	Correct	211 ms	14056 KB	Output is correct
29	Correct	282 ms	10728 KB	Output is correct
30	Correct	205 ms	14060 KB	Output is correct
31	Correct	301 ms	10720 KB	Output is correct

Subtask #5
46.0 / 46.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	7 ms	5240 KB	Output is correct
3	Correct	7 ms	5240 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	8 ms	5240 KB	Output is correct
6	Correct	8 ms	5240 KB	Output is correct
7	Correct	6 ms	5112 KB	Output is correct
8	Correct	6 ms	5112 KB	Output is correct
9	Correct	8 ms	5240 KB	Output is correct
10	Correct	8 ms	5240 KB	Output is correct
11	Correct	8 ms	5244 KB	Output is correct
12	Correct	7 ms	5240 KB	Output is correct
13	Correct	9 ms	5212 KB	Output is correct
14	Correct	8 ms	5316 KB	Output is correct
15	Correct	8 ms	5244 KB	Output is correct
16	Correct	663 ms	22092 KB	Output is correct
17	Correct	2229 ms	32256 KB	Output is correct
18	Correct	94 ms	7736 KB	Output is correct
19	Correct	289 ms	20660 KB	Output is correct
20	Correct	2066 ms	32324 KB	Output is correct
21	Correct	1004 ms	25324 KB	Output is correct
22	Correct	468 ms	23408 KB	Output is correct
23	Correct	2049 ms	32356 KB	Output is correct
24	Correct	2041 ms	32092 KB	Output is correct
25	Correct	2051 ms	32056 KB	Output is correct
26	Correct	293 ms	20264 KB	Output is correct
27	Correct	285 ms	20244 KB	Output is correct
28	Correct	304 ms	20392 KB	Output is correct
29	Correct	307 ms	20660 KB	Output is correct
30	Correct	278 ms	20564 KB	Output is correct
31	Correct	5 ms	5112 KB	Output is correct
32	Correct	6 ms	5112 KB	Output is correct
33	Correct	6 ms	5064 KB	Output is correct
34	Correct	6 ms	5084 KB	Output is correct
35	Correct	6 ms	5112 KB	Output is correct
36	Correct	6 ms	5112 KB	Output is correct
37	Correct	6 ms	5112 KB	Output is correct
38	Correct	6 ms	5112 KB	Output is correct
39	Correct	6 ms	5112 KB	Output is correct
40	Correct	6 ms	5112 KB	Output is correct
41	Correct	921 ms	13680 KB	Output is correct
42	Correct	1759 ms	22296 KB	Output is correct
43	Correct	1816 ms	22136 KB	Output is correct
44	Correct	307 ms	10944 KB	Output is correct
45	Correct	1699 ms	22032 KB	Output is correct
46	Correct	1814 ms	22104 KB	Output is correct
47	Correct	1827 ms	22116 KB	Output is correct
48	Correct	1822 ms	21952 KB	Output is correct
49	Correct	1818 ms	22112 KB	Output is correct
50	Correct	1736 ms	22136 KB	Output is correct
51	Correct	1789 ms	21976 KB	Output is correct
52	Correct	1816 ms	21968 KB	Output is correct
53	Correct	1824 ms	21524 KB	Output is correct
54	Correct	1776 ms	21580 KB	Output is correct
55	Correct	1718 ms	21576 KB	Output is correct
56	Correct	1805 ms	21492 KB	Output is correct
57	Correct	1867 ms	21516 KB	Output is correct
58	Correct	1867 ms	21568 KB	Output is correct
59	Correct	240 ms	10776 KB	Output is correct
60	Correct	1834 ms	21640 KB	Output is correct
61	Correct	1365 ms	22560 KB	Output is correct
62	Correct	211 ms	14092 KB	Output is correct
63	Correct	226 ms	10556 KB	Output is correct
64	Correct	212 ms	14188 KB	Output is correct
65	Correct	208 ms	14188 KB	Output is correct
66	Correct	261 ms	10440 KB	Output is correct
67	Correct	288 ms	10728 KB	Output is correct
68	Correct	211 ms	14056 KB	Output is correct
69	Correct	282 ms	10728 KB	Output is correct
70	Correct	205 ms	14060 KB	Output is correct
71	Correct	301 ms	10720 KB	Output is correct
72	Correct	1151 ms	24608 KB	Output is correct
73	Correct	2092 ms	31536 KB	Output is correct
74	Correct	2122 ms	31416 KB	Output is correct
75	Correct	2041 ms	31336 KB	Output is correct
76	Correct	2079 ms	31228 KB	Output is correct
77	Correct	2062 ms	31428 KB	Output is correct
78	Correct	2087 ms	31372 KB	Output is correct
79	Correct	2059 ms	31320 KB	Output is correct
80	Correct	2059 ms	31304 KB	Output is correct
81	Correct	2051 ms	31252 KB	Output is correct
82	Correct	2106 ms	31304 KB	Output is correct
83	Correct	2053 ms	31260 KB	Output is correct
84	Correct	2043 ms	31224 KB	Output is correct
85	Correct	2059 ms	31224 KB	Output is correct
86	Correct	2099 ms	31360 KB	Output is correct
87	Correct	2017 ms	31236 KB	Output is correct
88	Correct	2029 ms	31288 KB	Output is correct
89	Correct	568 ms	23316 KB	Output is correct
90	Correct	2112 ms	31232 KB	Output is correct
91	Correct	1674 ms	31280 KB	Output is correct
92	Correct	304 ms	20088 KB	Output is correct
93	Correct	450 ms	21096 KB	Output is correct
94	Correct	290 ms	19436 KB	Output is correct
95	Correct	287 ms	20088 KB	Output is correct
96	Correct	462 ms	19180 KB	Output is correct
97	Correct	579 ms	21432 KB	Output is correct
98	Correct	299 ms	19832 KB	Output is correct
99	Correct	494 ms	21376 KB	Output is correct
100	Correct	272 ms	19672 KB	Output is correct

답안 #54065

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 13.0 / 13.0

Subtask #3 12.0 / 12.0

Subtask #4 19.0 / 19.0

Subtask #5 46.0 / 46.0

Subtask #1
10.0 / 10.0

Subtask #2
13.0 / 13.0

Subtask #3
12.0 / 12.0

Subtask #4
19.0 / 19.0

Subtask #5
46.0 / 46.0