oj.uz

답안 #213615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
213615 2020-03-26T09:22:56 Z someone_aa Evacuation plan (IZhO18_plan) C++17
100 / 100
 1064 ms 29412 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 100100;

class dsu {
public:
	int uparent[maxn], n;
	int usize[maxn];

	void init(int _n) {
		n = _n;
		for(int i=0;i<=n;i++) {
			uparent[i] = i;
			usize[i] = 1;
		}
	}
	int ufind(int x) {
		while(x != uparent[x]) 
			x = uparent[x];
		return x;
	}
	void unite(int x, int y) {
		x = ufind(x);
		y = ufind(y);

		if(x == y) return;

		if(usize[x] > usize[y]) {
			uparent[y] = x;
			usize[x] += usize[y];
		}
		else {
			uparent[x] = y;
			usize[y] += usize[x];
		}
	}
}D;

int n, m, k, q, sz;
int result[maxn];
int dist[maxn];
bool visited[maxn];
vector<int>v; // NPP indexes
vector<pair<int,int> > g[maxn];
void get_distances() {
	for(int i=0;i<=n;i++) {
		visited[i] = false;
		dist[i] = INT_MAX;
	}

	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for(int i:v) {
		dist[i] = 0;
		pq.push(mp(0, i));
	}

	while(!pq.empty()) {
		int node = pq.top().second;
		int curr = pq.top().first;
		pq.pop();

		if(visited[node]) continue;
		visited[node] = true;

		for(auto i:g[node]) {
			if(!visited[i.first] && dist[i.first] > curr + i.second) {
				dist[i.first] = curr + i.second;
				pq.push(mp(dist[i.first], i.first));
			}
		}
	}
}

int orgval[maxn];
vector<int>indexes[maxn];
map<int, int>cind;
set<int>st;
void preprocess() {
	for(int i=1;i<=n;i++) {
		st.insert(dist[i]);
	}

	int br = 0;
	for(int i:st) {
		cind[i] = br;
		orgval[br] = i;
		br++;
	}
	sz = br;

	for(int i=1;i<=n;i++) {
		indexes[cind[dist[i]]].pb(i);
	}
}

int ql[maxn], qr[maxn];
int qs[maxn], qt[maxn];
bool answ[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	int a, b, c;
	for(int i=0;i<m;i++) {
		cin>>a>>b>>c;
		g[a].pb(mp(b, c));
		g[b].pb(mp(a, c));
	}
	int x;
	cin>>k;
	for(int i=0;i<k;i++) {
		cin>>x;
		v.pb(x);
	}

	get_distances();
	preprocess();

	cin>>q;
	for(int i=1;i<=q;i++) {
		cin>>qs[i]>>qt[i];
		ql[i] = -1, qr[i] = sz;
	}

	for(int d=0;d<20;d++) {
		//cout<<"At level: "<<d<<"\n";
		D.init(n);

		vector<int>qrs[maxn];
		memset(answ,false,sizeof(answ));

		//cout<<"Queries at beginning\n";
		for(int i=1;i<=q;i++) {
			int mid = (ql[i] + qr[i]) / 2;
			if(qr[i] - ql[i] <= 1) {
				result[i] = orgval[ql[i]];
				continue;
			}
			qrs[mid].pb(i);
		}

		for(int j=sz-1;j>=0;j--) {
			for(int i:indexes[j]) {
				for(auto nxt:g[i]) {
					if(dist[i] <= dist[nxt.first]) {
						D.unite(i, nxt.first);
					}
				}
			}

			for(int i:qrs[j]) {
				if(D.ufind(qs[i]) == D.ufind(qt[i])) {
					answ[i] = true;
				}
			}
		}

		for(int i=1;i<=q;i++) {
			if(qr[i] - ql[i] <= 1) continue;

			int mid = (ql[i] + qr[i]) / 2;
			if(answ[i]) {
				ql[i] = mid;
			}
			else {
				qr[i] = mid;
			}
		}
	}

	for(int i=1;i<=q;i++) {
		cout<<result[i]<<"\n";
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7552 KB Output is correct
2 Correct 14 ms 7680 KB Output is correct
3 Correct 13 ms 7680 KB Output is correct
4 Correct 12 ms 7552 KB Output is correct
5 Correct 13 ms 7680 KB Output is correct
6 Correct 15 ms 7680 KB Output is correct
7 Correct 12 ms 7552 KB Output is correct
8 Correct 12 ms 7552 KB Output is correct
9 Correct 14 ms 7808 KB Output is correct
10 Correct 13 ms 7680 KB Output is correct
11 Correct 16 ms 7808 KB Output is correct
12 Correct 13 ms 7680 KB Output is correct
13 Correct 18 ms 7820 KB Output is correct
14 Correct 14 ms 7804 KB Output is correct
15 Correct 15 ms 7808 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7552 KB Output is correct
2 Correct 14 ms 7680 KB Output is correct
3 Correct 13 ms 7680 KB Output is correct
4 Correct 12 ms 7552 KB Output is correct
5 Correct 13 ms 7680 KB Output is correct
6 Correct 15 ms 7680 KB Output is correct
7 Correct 12 ms 7552 KB Output is correct
8 Correct 12 ms 7552 KB Output is correct
9 Correct 14 ms 7808 KB Output is correct
10 Correct 13 ms 7680 KB Output is correct
11 Correct 16 ms 7808 KB Output is correct
12 Correct 13 ms 7680 KB Output is correct
13 Correct 18 ms 7820 KB Output is correct
14 Correct 14 ms 7804 KB Output is correct
15 Correct 15 ms 7808 KB Output is correct
16 Correct 395 ms 16824 KB Output is correct
17 Correct 1051 ms 27112 KB Output is correct
18 Correct 70 ms 9884 KB Output is correct
19 Correct 205 ms 17116 KB Output is correct
20 Correct 1014 ms 27256 KB Output is correct
21 Correct 498 ms 19648 KB Output is correct
22 Correct 622 ms 29412 KB Output is correct
23 Correct 1006 ms 27148 KB Output is correct
24 Correct 1046 ms 27268 KB Output is correct
25 Correct 1002 ms 27076 KB Output is correct
26 Correct 222 ms 17184 KB Output is correct
27 Correct 203 ms 16984 KB Output is correct
28 Correct 211 ms 16992 KB Output is correct
29 Correct 217 ms 17232 KB Output is correct
30 Correct 200 ms 17236 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 598 ms 16624 KB Output is correct
2 Correct 946 ms 23920 KB Output is correct
3 Correct 948 ms 23944 KB Output is correct
4 Correct 489 ms 25464 KB Output is correct
5 Correct 945 ms 23828 KB Output is correct
6 Correct 962 ms 24008 KB Output is correct
7 Correct 957 ms 23944 KB Output is correct
8 Correct 946 ms 23880 KB Output is correct
9 Correct 959 ms 24076 KB Output is correct
10 Correct 998 ms 23688 KB Output is correct
11 Correct 938 ms 23816 KB Output is correct
12 Correct 947 ms 23700 KB Output is correct
13 Correct 1012 ms 23708 KB Output is correct
14 Correct 946 ms 23676 KB Output is correct
15 Correct 946 ms 23568 KB Output is correct
16 Correct 944 ms 23536 KB Output is correct
17 Correct 984 ms 23684 KB Output is correct
18 Correct 951 ms 23304 KB Output is correct
19 Correct 444 ms 24824 KB Output is correct
20 Correct 958 ms 23436 KB Output is correct
21 Correct 737 ms 24056 KB Output is correct
22 Correct 148 ms 13404 KB Output is correct
23 Correct 369 ms 20916 KB Output is correct
24 Correct 171 ms 13416 KB Output is correct
25 Correct 172 ms 13400 KB Output is correct
26 Correct 422 ms 16396 KB Output is correct
27 Correct 523 ms 24824 KB Output is correct
28 Correct 152 ms 13420 KB Output is correct
29 Correct 487 ms 24952 KB Output is correct
30 Correct 152 ms 13396 KB Output is correct
31 Correct 508 ms 24824 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 7552 KB Output is correct
2 Correct 14 ms 7680 KB Output is correct
3 Correct 13 ms 7680 KB Output is correct
4 Correct 12 ms 7552 KB Output is correct
5 Correct 13 ms 7680 KB Output is correct
6 Correct 15 ms 7680 KB Output is correct
7 Correct 12 ms 7552 KB Output is correct
8 Correct 12 ms 7552 KB Output is correct
9 Correct 14 ms 7808 KB Output is correct
10 Correct 13 ms 7680 KB Output is correct
11 Correct 16 ms 7808 KB Output is correct
12 Correct 13 ms 7680 KB Output is correct
13 Correct 18 ms 7820 KB Output is correct
14 Correct 14 ms 7804 KB Output is correct
15 Correct 15 ms 7808 KB Output is correct
16 Correct 395 ms 16824 KB Output is correct
17 Correct 1051 ms 27112 KB Output is correct
18 Correct 70 ms 9884 KB Output is correct
19 Correct 205 ms 17116 KB Output is correct
20 Correct 1014 ms 27256 KB Output is correct
21 Correct 498 ms 19648 KB Output is correct
22 Correct 622 ms 29412 KB Output is correct
23 Correct 1006 ms 27148 KB Output is correct
24 Correct 1046 ms 27268 KB Output is correct
25 Correct 1002 ms 27076 KB Output is correct
26 Correct 222 ms 17184 KB Output is correct
27 Correct 203 ms 16984 KB Output is correct
28 Correct 211 ms 16992 KB Output is correct
29 Correct 217 ms 17232 KB Output is correct
30 Correct 200 ms 17236 KB Output is correct
31 Correct 12 ms 7552 KB Output is correct
32 Correct 12 ms 7552 KB Output is correct
33 Correct 12 ms 7552 KB Output is correct
34 Correct 12 ms 7552 KB Output is correct
35 Correct 12 ms 7552 KB Output is correct
36 Correct 12 ms 7552 KB Output is correct
37 Correct 12 ms 7552 KB Output is correct
38 Correct 12 ms 7552 KB Output is correct
39 Correct 12 ms 7552 KB Output is correct
40 Correct 12 ms 7552 KB Output is correct
41 Correct 598 ms 16624 KB Output is correct
42 Correct 946 ms 23920 KB Output is correct
43 Correct 948 ms 23944 KB Output is correct
44 Correct 489 ms 25464 KB Output is correct
45 Correct 945 ms 23828 KB Output is correct
46 Correct 962 ms 24008 KB Output is correct
47 Correct 957 ms 23944 KB Output is correct
48 Correct 946 ms 23880 KB Output is correct
49 Correct 959 ms 24076 KB Output is correct
50 Correct 998 ms 23688 KB Output is correct
51 Correct 938 ms 23816 KB Output is correct
52 Correct 947 ms 23700 KB Output is correct
53 Correct 1012 ms 23708 KB Output is correct
54 Correct 946 ms 23676 KB Output is correct
55 Correct 946 ms 23568 KB Output is correct
56 Correct 944 ms 23536 KB Output is correct
57 Correct 984 ms 23684 KB Output is correct
58 Correct 951 ms 23304 KB Output is correct
59 Correct 444 ms 24824 KB Output is correct
60 Correct 958 ms 23436 KB Output is correct
61 Correct 737 ms 24056 KB Output is correct
62 Correct 148 ms 13404 KB Output is correct
63 Correct 369 ms 20916 KB Output is correct
64 Correct 171 ms 13416 KB Output is correct
65 Correct 172 ms 13400 KB Output is correct
66 Correct 422 ms 16396 KB Output is correct
67 Correct 523 ms 24824 KB Output is correct
68 Correct 152 ms 13420 KB Output is correct
69 Correct 487 ms 24952 KB Output is correct
70 Correct 152 ms 13396 KB Output is correct
71 Correct 508 ms 24824 KB Output is correct
72 Correct 665 ms 19220 KB Output is correct
73 Correct 1054 ms 26664 KB Output is correct
74 Correct 1050 ms 26632 KB Output is correct
75 Correct 1056 ms 26632 KB Output is correct
76 Correct 1050 ms 26724 KB Output is correct
77 Correct 1046 ms 26628 KB Output is correct
78 Correct 1043 ms 26636 KB Output is correct
79 Correct 1044 ms 26760 KB Output is correct
80 Correct 1064 ms 26692 KB Output is correct
81 Correct 1042 ms 26808 KB Output is correct
82 Correct 1037 ms 26760 KB Output is correct
83 Correct 1028 ms 26640 KB Output is correct
84 Correct 1039 ms 26676 KB Output is correct
85 Correct 1041 ms 26604 KB Output is correct
86 Correct 1049 ms 26632 KB Output is correct
87 Correct 1051 ms 26628 KB Output is correct
88 Correct 1037 ms 26576 KB Output is correct
89 Correct 623 ms 28844 KB Output is correct
90 Correct 1046 ms 26572 KB Output is correct
91 Correct 781 ms 26844 KB Output is correct
92 Correct 205 ms 16524 KB Output is correct
93 Correct 525 ms 24476 KB Output is correct
94 Correct 208 ms 16520 KB Output is correct
95 Correct 213 ms 16604 KB Output is correct
96 Correct 452 ms 19252 KB Output is correct
97 Correct 678 ms 28204 KB Output is correct
98 Correct 208 ms 16480 KB Output is correct
99 Correct 627 ms 28252 KB Output is correct
100 Correct 204 ms 16600 KB Output is correct