oj.uz

Submission #930226

# Submission time Handle Problem Language Result Execution time Memory
930226 2024-02-19T05:53:08 Z vjudge1 Evacuation plan (IZhO18_plan) C++17
100 / 100
 697 ms 164208 KB 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define pb push_back
#define ent "\n"

#define int long long

const int maxn = (int)1e6 + 13;
const ll inf = (long long)1e18 + 20;
const int mod = (int)1e9 + 7;

int n,m,k,q;
int ans[maxn];
vector<pair<int,int>>g[maxn];
int a[maxn],b[maxn],c[maxn];
int dst[maxn];
int pr[maxn];
int sz[maxn];
int x[maxn],y[maxn];
pair<int,int>qur[maxn];
vector<int>pos[maxn],mid[maxn];
int rev[maxn];

int get(int x){
	if(x == pr[x])return x;
	return pr[x] = get(pr[x]);
}

void unite(int x,int y){
	x = get(x),y= get(y);
	if(x == y)return ;
	if(sz[x] > sz[y])swap(x,y);
	pr[x] = y;
	sz[y] += sz[x];
}

void solve(){
	cin >> n >> m ;
	for(int i = 1 ; i <= m ; i++){
		int x,y,w;cin >> x >> y >> w;
		g[x].pb({y,w});
		g[y].pb({x,w});
		a[i] = x,b[i] = y,c[i] = w;
	}
	cin >> k;
	set<pair<int,int>>s;
	for(int i = 1 ; i <= n ; i ++){
		dst[i] = inf;
		pr[i] = i;
	}
	for(int i = 1 ; i <= k ; i ++){
		int x;cin >> x;
		s.insert({0,x});
		dst[x] = 0;
	}
	while(s.size()){
		pair<int,int>v = *s.begin();
		s.erase(v);
		for(auto to : g[v.second]){
			int val = dst[v.second] + to.second;
			if(dst[to.first] > val){
				dst[to.first] = val;
				s.insert({val,to.first});
			}
		}
	}
	vector<int>comp;
	for(int i = 1 ; i <= n ; i ++){
		comp.pb(dst[i]);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)),comp.end());
	for(int i = 1 ; i <= n ; i ++){
		int orig = dst[i];
		dst[i] = upper_bound(all(comp),dst[i]) - comp.begin();
		rev[dst[i]] = orig;
	}
	for(int i = 1 ; i <= m ; i ++){
		pos[min(dst[a[i]],dst[b[i]])].pb(i);
	}
	cin >> q;
	for(int i = 1 ; i <= q ; i ++){
		cin >> x[i] >> y[i];
		qur[i] = {1,comp.size()};
	}
	for(int I = 1 ; I <= 25 ; I ++){
		for(int i = 0 ; i <= n ; i ++){
			pr[i] = i;
			sz[i] = 1;
			mid[i].clear();
		}
		for(int i = 1 ; i <= q ; i ++){
			if(qur[i].first <= qur[i].second){
				int m = (qur[i].first + qur[i].second) >> 1;
				mid[m].pb(i);			
			}
		}
		for(int i = comp.size() ; i >= 1 ; i --){
			for(auto to : pos[i]){
				unite(a[to],b[to]);
			}
			for(auto to : mid[i]){
				if(get(x[to]) == get(y[to])){
					qur[to].first = i + 1;
					//ans[to] = i;
				}
				else{
					qur[to].second = i - 1;
				}
			}
		}
	}
	for(int i = 1 ; i <= q ;  i++){
		cout << rev[qur[i].first - 1] << ent;
	}
}

signed main(){
	// freopen ("hps.in", "r", stdin);
	// freopen ("hps.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	int test = 0;
	while(t --){
	//	cout << "Case " << ++test << ": ";
		solve();
	}
	return 0;
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:158:6: warning: unused variable 'test' [-Wunused-variable]
  158 |  int test = 0;
      |      ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 92752 KB Output is correct
2 Correct 23 ms 92764 KB Output is correct
3 Correct 19 ms 92764 KB Output is correct
4 Correct 19 ms 92764 KB Output is correct
5 Correct 20 ms 92980 KB Output is correct
6 Correct 19 ms 93016 KB Output is correct
7 Correct 18 ms 92620 KB Output is correct
8 Correct 18 ms 92764 KB Output is correct
9 Correct 20 ms 93020 KB Output is correct
10 Correct 20 ms 92764 KB Output is correct
11 Correct 20 ms 93272 KB Output is correct
12 Correct 19 ms 92880 KB Output is correct
13 Correct 20 ms 92892 KB Output is correct
14 Correct 20 ms 93020 KB Output is correct
15 Correct 20 ms 93276 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 92752 KB Output is correct
2 Correct 23 ms 92764 KB Output is correct
3 Correct 19 ms 92764 KB Output is correct
4 Correct 19 ms 92764 KB Output is correct
5 Correct 20 ms 92980 KB Output is correct
6 Correct 19 ms 93016 KB Output is correct
7 Correct 18 ms 92620 KB Output is correct
8 Correct 18 ms 92764 KB Output is correct
9 Correct 20 ms 93020 KB Output is correct
10 Correct 20 ms 92764 KB Output is correct
11 Correct 20 ms 93272 KB Output is correct
12 Correct 19 ms 92880 KB Output is correct
13 Correct 20 ms 92892 KB Output is correct
14 Correct 20 ms 93020 KB Output is correct
15 Correct 20 ms 93276 KB Output is correct
16 Correct 201 ms 121964 KB Output is correct
17 Correct 657 ms 163704 KB Output is correct
18 Correct 58 ms 99412 KB Output is correct
19 Correct 144 ms 122224 KB Output is correct
20 Correct 649 ms 163940 KB Output is correct
21 Correct 264 ms 131116 KB Output is correct
22 Correct 190 ms 133336 KB Output is correct
23 Correct 597 ms 164112 KB Output is correct
24 Correct 641 ms 163996 KB Output is correct
25 Correct 610 ms 162880 KB Output is correct
26 Correct 147 ms 122820 KB Output is correct
27 Correct 144 ms 122020 KB Output is correct
28 Correct 149 ms 122712 KB Output is correct
29 Correct 143 ms 121548 KB Output is correct
30 Correct 147 ms 122188 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 92760 KB Output is correct
2 Correct 19 ms 92708 KB Output is correct
3 Correct 19 ms 92720 KB Output is correct
4 Correct 19 ms 92764 KB Output is correct
5 Correct 19 ms 92692 KB Output is correct
6 Correct 19 ms 92760 KB Output is correct
7 Correct 19 ms 92764 KB Output is correct
8 Correct 18 ms 92764 KB Output is correct
9 Correct 18 ms 92764 KB Output is correct
10 Correct 18 ms 92764 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 118536 KB Output is correct
2 Correct 551 ms 150380 KB Output is correct
3 Correct 544 ms 149972 KB Output is correct
4 Correct 104 ms 111412 KB Output is correct
5 Correct 590 ms 151008 KB Output is correct
6 Correct 522 ms 150036 KB Output is correct
7 Correct 535 ms 149856 KB Output is correct
8 Correct 539 ms 150064 KB Output is correct
9 Correct 488 ms 150532 KB Output is correct
10 Correct 564 ms 150440 KB Output is correct
11 Correct 538 ms 150448 KB Output is correct
12 Correct 547 ms 150608 KB Output is correct
13 Correct 535 ms 150080 KB Output is correct
14 Correct 557 ms 150280 KB Output is correct
15 Correct 491 ms 150260 KB Output is correct
16 Correct 500 ms 150100 KB Output is correct
17 Correct 565 ms 150012 KB Output is correct
18 Correct 538 ms 150112 KB Output is correct
19 Correct 102 ms 111300 KB Output is correct
20 Correct 547 ms 150208 KB Output is correct
21 Correct 421 ms 150704 KB Output is correct
22 Correct 118 ms 111552 KB Output is correct
23 Correct 161 ms 110504 KB Output is correct
24 Correct 114 ms 111300 KB Output is correct
25 Correct 113 ms 111372 KB Output is correct
26 Correct 141 ms 110152 KB Output is correct
27 Correct 109 ms 111404 KB Output is correct
28 Correct 114 ms 112232 KB Output is correct
29 Correct 114 ms 111300 KB Output is correct
30 Correct 116 ms 111332 KB Output is correct
31 Correct 106 ms 111384 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 92752 KB Output is correct
2 Correct 23 ms 92764 KB Output is correct
3 Correct 19 ms 92764 KB Output is correct
4 Correct 19 ms 92764 KB Output is correct
5 Correct 20 ms 92980 KB Output is correct
6 Correct 19 ms 93016 KB Output is correct
7 Correct 18 ms 92620 KB Output is correct
8 Correct 18 ms 92764 KB Output is correct
9 Correct 20 ms 93020 KB Output is correct
10 Correct 20 ms 92764 KB Output is correct
11 Correct 20 ms 93272 KB Output is correct
12 Correct 19 ms 92880 KB Output is correct
13 Correct 20 ms 92892 KB Output is correct
14 Correct 20 ms 93020 KB Output is correct
15 Correct 20 ms 93276 KB Output is correct
16 Correct 201 ms 121964 KB Output is correct
17 Correct 657 ms 163704 KB Output is correct
18 Correct 58 ms 99412 KB Output is correct
19 Correct 144 ms 122224 KB Output is correct
20 Correct 649 ms 163940 KB Output is correct
21 Correct 264 ms 131116 KB Output is correct
22 Correct 190 ms 133336 KB Output is correct
23 Correct 597 ms 164112 KB Output is correct
24 Correct 641 ms 163996 KB Output is correct
25 Correct 610 ms 162880 KB Output is correct
26 Correct 147 ms 122820 KB Output is correct
27 Correct 144 ms 122020 KB Output is correct
28 Correct 149 ms 122712 KB Output is correct
29 Correct 143 ms 121548 KB Output is correct
30 Correct 147 ms 122188 KB Output is correct
31 Correct 20 ms 92760 KB Output is correct
32 Correct 19 ms 92708 KB Output is correct
33 Correct 19 ms 92720 KB Output is correct
34 Correct 19 ms 92764 KB Output is correct
35 Correct 19 ms 92692 KB Output is correct
36 Correct 19 ms 92760 KB Output is correct
37 Correct 19 ms 92764 KB Output is correct
38 Correct 18 ms 92764 KB Output is correct
39 Correct 18 ms 92764 KB Output is correct
40 Correct 18 ms 92764 KB Output is correct
41 Correct 256 ms 118536 KB Output is correct
42 Correct 551 ms 150380 KB Output is correct
43 Correct 544 ms 149972 KB Output is correct
44 Correct 104 ms 111412 KB Output is correct
45 Correct 590 ms 151008 KB Output is correct
46 Correct 522 ms 150036 KB Output is correct
47 Correct 535 ms 149856 KB Output is correct
48 Correct 539 ms 150064 KB Output is correct
49 Correct 488 ms 150532 KB Output is correct
50 Correct 564 ms 150440 KB Output is correct
51 Correct 538 ms 150448 KB Output is correct
52 Correct 547 ms 150608 KB Output is correct
53 Correct 535 ms 150080 KB Output is correct
54 Correct 557 ms 150280 KB Output is correct
55 Correct 491 ms 150260 KB Output is correct
56 Correct 500 ms 150100 KB Output is correct
57 Correct 565 ms 150012 KB Output is correct
58 Correct 538 ms 150112 KB Output is correct
59 Correct 102 ms 111300 KB Output is correct
60 Correct 547 ms 150208 KB Output is correct
61 Correct 421 ms 150704 KB Output is correct
62 Correct 118 ms 111552 KB Output is correct
63 Correct 161 ms 110504 KB Output is correct
64 Correct 114 ms 111300 KB Output is correct
65 Correct 113 ms 111372 KB Output is correct
66 Correct 141 ms 110152 KB Output is correct
67 Correct 109 ms 111404 KB Output is correct
68 Correct 114 ms 112232 KB Output is correct
69 Correct 114 ms 111300 KB Output is correct
70 Correct 116 ms 111332 KB Output is correct
71 Correct 106 ms 111384 KB Output is correct
72 Correct 322 ms 133452 KB Output is correct
73 Correct 658 ms 163780 KB Output is correct
74 Correct 660 ms 163788 KB Output is correct
75 Correct 628 ms 163988 KB Output is correct
76 Correct 614 ms 163944 KB Output is correct
77 Correct 608 ms 163820 KB Output is correct
78 Correct 583 ms 163408 KB Output is correct
79 Correct 583 ms 163544 KB Output is correct
80 Correct 600 ms 163720 KB Output is correct
81 Correct 643 ms 163872 KB Output is correct
82 Correct 668 ms 163384 KB Output is correct
83 Correct 606 ms 163800 KB Output is correct
84 Correct 697 ms 163092 KB Output is correct
85 Correct 610 ms 162616 KB Output is correct
86 Correct 586 ms 163420 KB Output is correct
87 Correct 619 ms 164208 KB Output is correct
88 Correct 589 ms 163780 KB Output is correct
89 Correct 177 ms 133960 KB Output is correct
90 Correct 630 ms 163948 KB Output is correct
91 Correct 423 ms 161072 KB Output is correct
92 Correct 149 ms 121440 KB Output is correct
93 Correct 230 ms 129600 KB Output is correct
94 Correct 159 ms 122852 KB Output is correct
95 Correct 169 ms 121388 KB Output is correct
96 Correct 202 ms 126748 KB Output is correct
97 Correct 185 ms 132092 KB Output is correct
98 Correct 164 ms 121228 KB Output is correct
99 Correct 184 ms 131908 KB Output is correct
100 Correct 146 ms 121720 KB Output is correct