oj.uz

Submission #893495

# Submission time Handle Problem Language Result Execution time Memory
893495 2023-12-27T05:52:42 Z vjudge1 Evacuation plan (IZhO18_plan) C++17
100 / 100
 672 ms 98292 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt")


typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back

const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(6e5)+100;
const long long inf = 2e18;
const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }

ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}


void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }

int n, m, k, q, qu[N], qv[N], qw[N], par[N], qs[N], qt[N], siz[N], dis[N], bl[N], br[N];
vector<int> pos[N];
vector<int> check[N];
vector<pair<int, int> > g[N];
vector<int> nuc;

int findpar(int v) {
	if(v == par[v]) return v;
	return par[v] = findpar(par[v]);
}

void combine(int a, int b) {
	a = findpar(a);
	b = findpar(b);
	if(a != b) {
		if(siz[a] < siz[b]) swap(a, b);
		par[b] = a;
		siz[a] += siz[b];
	}
}

void Baizho() {	
	cin>>n>>m;
	for(int i = 1; i <= m; i ++) {
		cin>>qu[i]>>qv[i]>>qw[i];
		g[qu[i]].pb({qv[i], qw[i]});
		g[qv[i]].pb({qu[i], qw[i]});
	}
	for(int i = 1; i <= n; i ++) {
		dis[i] = 2e9;
	}
	cin>>k;
	set<pair<int, int> > st;
	for(int i = 1; i <= k; i ++) {
		int x; cin>>x;
		nuc.pb(x);
		dis[x] = 0;
		st.insert({dis[x], x});
	}
	while(!st.empty()) {
		int v = (*st.begin()).ss;
		st.erase(st.begin());
		for(auto to : g[v]) {
			if(dis[to.ff] > dis[v] + to.ss) {
				if(dis[to.ff] != 2e9) st.erase({dis[to.ff], to.ff});
				dis[to.ff] = dis[v] + to.ss;
				st.insert({dis[to.ff], to.ff});
			}
		}
	}
	vector<int> comp;
	map<int, int> rev;
	for(int i = 1; i <= n; i ++) {
		comp.pb(dis[i]);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)), comp.end());
	for(int i = 1; i <= n;  i ++) {
		int orig = dis[i];
		dis[i] = upper_bound(all(comp), dis[i]) - comp.begin();
		rev[dis[i]] = orig;
//		cout<<dis[i]<<" ";
	}
//	cout<<"\n";
	for(int i = 1; i <= m; i ++) {
		pos[min(dis[qu[i]], dis[qv[i]])].pb(i);
	}
	cin>>q;
	for(int i = 1; i <= q; i ++) {
		cin>>qs[i]>>qt[i];
		bl[i] = 1, br[i] = comp.sz;
//		int l = 1, r = comp.sz;
//		while(l <= r) {
//			int mid = (l + r) / 2;
//			for(int j = 0; j <= n; j ++) {
//				par[j] = j;
//				siz[j] = 1;
//				ok[j] = 0;
//			}
//			for(int j = 1; j <= n; j ++) {
//				if(dis[j] >= mid) ok[j] = 1;
//			}
//			for(int j = 1; j <= m; j ++) {
//				if(ok[qu[j]] && ok[qv[j]]) combine(qu[j], qv[j]);
// 				dis[qu[j]] >= mid && dis[qv[j]] >= mid
//				min() >= mid
//			}
//			if(findpar(qs[i]) == findpar(qt[i])) l = mid + 1;
//			else r = mid - 1;
//		}
//		cout<<rev[l - 1]<<"\n";
	}
	for(int bin = 0; bin <= 35; bin ++) {
		for(int j = 0; j <= n; j ++) {
			par[j] = j;
			siz[j] = 1;
			check[j].clear();
		}
		for(int i = 1; i <= q; i ++) {
			if(bl[i] <= br[i]) {
				check[(bl[i] + br[i]) / 2].pb(i);
//				cout<<i<<" "<<bl[i]<<br[i]<<"OLOY \n";
			}
		}
		for(int i = comp.sz; i >= 1; i --) {
			for(auto j : pos[i]) {
				combine(qu[j], qv[j]);
//				cout<<j<<" "<<i<<" "<<qu[j]<<" "<<qv[j]<<"\n";
			}
			for(auto j : check[i]) {
				if(findpar(qs[j]) == findpar(qt[j])) {
					bl[j] = i + 1;
//					cout<<j<<" "<<i<<"\n";
				}
				else br[j] = i - 1;
			}
		}
	}
	for(int i = 1; i <= q; i ++) cout<<rev[bl[i] - 1]<<"\n";
}
 
signed main() {		
 
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;

    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

plan.cpp: In function 'void Freopen(std::string)':
plan.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62044 KB Output is correct
2 Correct 13 ms 62300 KB Output is correct
3 Correct 13 ms 62316 KB Output is correct
4 Correct 12 ms 62044 KB Output is correct
5 Correct 13 ms 62300 KB Output is correct
6 Correct 13 ms 62044 KB Output is correct
7 Correct 11 ms 62044 KB Output is correct
8 Correct 12 ms 62044 KB Output is correct
9 Correct 13 ms 62300 KB Output is correct
10 Correct 13 ms 62204 KB Output is correct
11 Correct 16 ms 62356 KB Output is correct
12 Correct 13 ms 62300 KB Output is correct
13 Correct 13 ms 62340 KB Output is correct
14 Correct 13 ms 62604 KB Output is correct
15 Correct 13 ms 62296 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62044 KB Output is correct
2 Correct 13 ms 62300 KB Output is correct
3 Correct 13 ms 62316 KB Output is correct
4 Correct 12 ms 62044 KB Output is correct
5 Correct 13 ms 62300 KB Output is correct
6 Correct 13 ms 62044 KB Output is correct
7 Correct 11 ms 62044 KB Output is correct
8 Correct 12 ms 62044 KB Output is correct
9 Correct 13 ms 62300 KB Output is correct
10 Correct 13 ms 62204 KB Output is correct
11 Correct 16 ms 62356 KB Output is correct
12 Correct 13 ms 62300 KB Output is correct
13 Correct 13 ms 62340 KB Output is correct
14 Correct 13 ms 62604 KB Output is correct
15 Correct 13 ms 62296 KB Output is correct
16 Correct 219 ms 76552 KB Output is correct
17 Correct 524 ms 98276 KB Output is correct
18 Correct 50 ms 64980 KB Output is correct
19 Correct 148 ms 78728 KB Output is correct
20 Correct 535 ms 97992 KB Output is correct
21 Correct 262 ms 82712 KB Output is correct
22 Correct 235 ms 89476 KB Output is correct
23 Correct 540 ms 98160 KB Output is correct
24 Correct 535 ms 98012 KB Output is correct
25 Correct 523 ms 97616 KB Output is correct
26 Correct 148 ms 77768 KB Output is correct
27 Correct 161 ms 78672 KB Output is correct
28 Correct 144 ms 77840 KB Output is correct
29 Correct 144 ms 78280 KB Output is correct
30 Correct 152 ms 78796 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 62044 KB Output is correct
2 Correct 12 ms 62044 KB Output is correct
3 Correct 11 ms 62044 KB Output is correct
4 Correct 11 ms 62044 KB Output is correct
5 Correct 12 ms 62044 KB Output is correct
6 Correct 12 ms 62044 KB Output is correct
7 Correct 11 ms 62044 KB Output is correct
8 Correct 12 ms 62044 KB Output is correct
9 Correct 11 ms 62044 KB Output is correct
10 Correct 12 ms 62044 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 73152 KB Output is correct
2 Correct 465 ms 83396 KB Output is correct
3 Correct 484 ms 83444 KB Output is correct
4 Correct 142 ms 75360 KB Output is correct
5 Correct 476 ms 83508 KB Output is correct
6 Correct 479 ms 83512 KB Output is correct
7 Correct 474 ms 83768 KB Output is correct
8 Correct 504 ms 83476 KB Output is correct
9 Correct 483 ms 83280 KB Output is correct
10 Correct 545 ms 83368 KB Output is correct
11 Correct 562 ms 83364 KB Output is correct
12 Correct 527 ms 83408 KB Output is correct
13 Correct 530 ms 83280 KB Output is correct
14 Correct 563 ms 83424 KB Output is correct
15 Correct 571 ms 83444 KB Output is correct
16 Correct 565 ms 83516 KB Output is correct
17 Correct 565 ms 83284 KB Output is correct
18 Correct 546 ms 83480 KB Output is correct
19 Correct 152 ms 75412 KB Output is correct
20 Correct 556 ms 83504 KB Output is correct
21 Correct 413 ms 83300 KB Output is correct
22 Correct 136 ms 72856 KB Output is correct
23 Correct 191 ms 72884 KB Output is correct
24 Correct 127 ms 72824 KB Output is correct
25 Correct 119 ms 72856 KB Output is correct
26 Correct 177 ms 70788 KB Output is correct
27 Correct 150 ms 75528 KB Output is correct
28 Correct 153 ms 72904 KB Output is correct
29 Correct 188 ms 75420 KB Output is correct
30 Correct 126 ms 72780 KB Output is correct
31 Correct 158 ms 75412 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 62044 KB Output is correct
2 Correct 13 ms 62300 KB Output is correct
3 Correct 13 ms 62316 KB Output is correct
4 Correct 12 ms 62044 KB Output is correct
5 Correct 13 ms 62300 KB Output is correct
6 Correct 13 ms 62044 KB Output is correct
7 Correct 11 ms 62044 KB Output is correct
8 Correct 12 ms 62044 KB Output is correct
9 Correct 13 ms 62300 KB Output is correct
10 Correct 13 ms 62204 KB Output is correct
11 Correct 16 ms 62356 KB Output is correct
12 Correct 13 ms 62300 KB Output is correct
13 Correct 13 ms 62340 KB Output is correct
14 Correct 13 ms 62604 KB Output is correct
15 Correct 13 ms 62296 KB Output is correct
16 Correct 219 ms 76552 KB Output is correct
17 Correct 524 ms 98276 KB Output is correct
18 Correct 50 ms 64980 KB Output is correct
19 Correct 148 ms 78728 KB Output is correct
20 Correct 535 ms 97992 KB Output is correct
21 Correct 262 ms 82712 KB Output is correct
22 Correct 235 ms 89476 KB Output is correct
23 Correct 540 ms 98160 KB Output is correct
24 Correct 535 ms 98012 KB Output is correct
25 Correct 523 ms 97616 KB Output is correct
26 Correct 148 ms 77768 KB Output is correct
27 Correct 161 ms 78672 KB Output is correct
28 Correct 144 ms 77840 KB Output is correct
29 Correct 144 ms 78280 KB Output is correct
30 Correct 152 ms 78796 KB Output is correct
31 Correct 11 ms 62044 KB Output is correct
32 Correct 12 ms 62044 KB Output is correct
33 Correct 11 ms 62044 KB Output is correct
34 Correct 11 ms 62044 KB Output is correct
35 Correct 12 ms 62044 KB Output is correct
36 Correct 12 ms 62044 KB Output is correct
37 Correct 11 ms 62044 KB Output is correct
38 Correct 12 ms 62044 KB Output is correct
39 Correct 11 ms 62044 KB Output is correct
40 Correct 12 ms 62044 KB Output is correct
41 Correct 272 ms 73152 KB Output is correct
42 Correct 465 ms 83396 KB Output is correct
43 Correct 484 ms 83444 KB Output is correct
44 Correct 142 ms 75360 KB Output is correct
45 Correct 476 ms 83508 KB Output is correct
46 Correct 479 ms 83512 KB Output is correct
47 Correct 474 ms 83768 KB Output is correct
48 Correct 504 ms 83476 KB Output is correct
49 Correct 483 ms 83280 KB Output is correct
50 Correct 545 ms 83368 KB Output is correct
51 Correct 562 ms 83364 KB Output is correct
52 Correct 527 ms 83408 KB Output is correct
53 Correct 530 ms 83280 KB Output is correct
54 Correct 563 ms 83424 KB Output is correct
55 Correct 571 ms 83444 KB Output is correct
56 Correct 565 ms 83516 KB Output is correct
57 Correct 565 ms 83284 KB Output is correct
58 Correct 546 ms 83480 KB Output is correct
59 Correct 152 ms 75412 KB Output is correct
60 Correct 556 ms 83504 KB Output is correct
61 Correct 413 ms 83300 KB Output is correct
62 Correct 136 ms 72856 KB Output is correct
63 Correct 191 ms 72884 KB Output is correct
64 Correct 127 ms 72824 KB Output is correct
65 Correct 119 ms 72856 KB Output is correct
66 Correct 177 ms 70788 KB Output is correct
67 Correct 150 ms 75528 KB Output is correct
68 Correct 153 ms 72904 KB Output is correct
69 Correct 188 ms 75420 KB Output is correct
70 Correct 126 ms 72780 KB Output is correct
71 Correct 158 ms 75412 KB Output is correct
72 Correct 362 ms 83432 KB Output is correct
73 Correct 672 ms 98024 KB Output is correct
74 Correct 656 ms 97984 KB Output is correct
75 Correct 646 ms 98044 KB Output is correct
76 Correct 643 ms 97920 KB Output is correct
77 Correct 627 ms 98292 KB Output is correct
78 Correct 610 ms 98136 KB Output is correct
79 Correct 610 ms 97992 KB Output is correct
80 Correct 633 ms 98084 KB Output is correct
81 Correct 597 ms 97996 KB Output is correct
82 Correct 648 ms 98020 KB Output is correct
83 Correct 602 ms 97936 KB Output is correct
84 Correct 606 ms 97812 KB Output is correct
85 Correct 625 ms 97536 KB Output is correct
86 Correct 584 ms 97944 KB Output is correct
87 Correct 586 ms 97984 KB Output is correct
88 Correct 577 ms 98040 KB Output is correct
89 Correct 236 ms 89508 KB Output is correct
90 Correct 500 ms 98044 KB Output is correct
91 Correct 385 ms 97164 KB Output is correct
92 Correct 149 ms 78744 KB Output is correct
93 Correct 248 ms 84296 KB Output is correct
94 Correct 143 ms 78276 KB Output is correct
95 Correct 153 ms 78252 KB Output is correct
96 Correct 214 ms 80132 KB Output is correct
97 Correct 217 ms 88144 KB Output is correct
98 Correct 147 ms 77912 KB Output is correct
99 Correct 239 ms 87988 KB Output is correct
100 Correct 140 ms 77808 KB Output is correct