oj.uz

답안 #938509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938509 2024-03-05T08:30:31 Z Baizho Evacuation plan (IZhO18_plan) C++14
100 / 100
 593 ms 98404 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;
//yo
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 62044 KB Output is correct
2 Correct 14 ms 62552 KB Output is correct
3 Correct 14 ms 62168 KB Output is correct
4 Correct 13 ms 62188 KB Output is correct
5 Correct 15 ms 62300 KB Output is correct
6 Correct 14 ms 62300 KB Output is correct
7 Correct 12 ms 62040 KB Output is correct
8 Correct 12 ms 62044 KB Output is correct
9 Correct 14 ms 62300 KB Output is correct
10 Correct 13 ms 62096 KB Output is correct
11 Correct 14 ms 62300 KB Output is correct
12 Correct 14 ms 62112 KB Output is correct
13 Correct 13 ms 62300 KB Output is correct
14 Correct 14 ms 62300 KB Output is correct
15 Correct 14 ms 62296 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 62044 KB Output is correct
2 Correct 14 ms 62552 KB Output is correct
3 Correct 14 ms 62168 KB Output is correct
4 Correct 13 ms 62188 KB Output is correct
5 Correct 15 ms 62300 KB Output is correct
6 Correct 14 ms 62300 KB Output is correct
7 Correct 12 ms 62040 KB Output is correct
8 Correct 12 ms 62044 KB Output is correct
9 Correct 14 ms 62300 KB Output is correct
10 Correct 13 ms 62096 KB Output is correct
11 Correct 14 ms 62300 KB Output is correct
12 Correct 14 ms 62112 KB Output is correct
13 Correct 13 ms 62300 KB Output is correct
14 Correct 14 ms 62300 KB Output is correct
15 Correct 14 ms 62296 KB Output is correct
16 Correct 228 ms 78564 KB Output is correct
17 Correct 573 ms 98252 KB Output is correct
18 Correct 52 ms 64852 KB Output is correct
19 Correct 152 ms 78924 KB Output is correct
20 Correct 542 ms 98108 KB Output is correct
21 Correct 270 ms 82552 KB Output is correct
22 Correct 237 ms 89420 KB Output is correct
23 Correct 541 ms 98244 KB Output is correct
24 Correct 593 ms 98008 KB Output is correct
25 Correct 527 ms 97808 KB Output is correct
26 Correct 146 ms 77764 KB Output is correct
27 Correct 160 ms 78676 KB Output is correct
28 Correct 150 ms 77812 KB Output is correct
29 Correct 149 ms 78276 KB Output is correct
30 Correct 145 ms 78788 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 62040 KB Output is correct
2 Correct 12 ms 62044 KB Output is correct
3 Correct 12 ms 62044 KB Output is correct
4 Correct 12 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 12 ms 62192 KB Output is correct
8 Correct 14 ms 62040 KB Output is correct
9 Correct 12 ms 62152 KB Output is correct
10 Correct 13 ms 62044 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 281 ms 76828 KB Output is correct
2 Correct 497 ms 91380 KB Output is correct
3 Correct 469 ms 91388 KB Output is correct
4 Correct 152 ms 77000 KB Output is correct
5 Correct 499 ms 91724 KB Output is correct
6 Correct 471 ms 91712 KB Output is correct
7 Correct 465 ms 91672 KB Output is correct
8 Correct 474 ms 91728 KB Output is correct
9 Correct 485 ms 91532 KB Output is correct
10 Correct 477 ms 91580 KB Output is correct
11 Correct 477 ms 91732 KB Output is correct
12 Correct 496 ms 91672 KB Output is correct
13 Correct 502 ms 91880 KB Output is correct
14 Correct 498 ms 91636 KB Output is correct
15 Correct 477 ms 91380 KB Output is correct
16 Correct 514 ms 91620 KB Output is correct
17 Correct 481 ms 91612 KB Output is correct
18 Correct 492 ms 91460 KB Output is correct
19 Correct 143 ms 77064 KB Output is correct
20 Correct 499 ms 91592 KB Output is correct
21 Correct 353 ms 92036 KB Output is correct
22 Correct 116 ms 74436 KB Output is correct
23 Correct 179 ms 74440 KB Output is correct
24 Correct 116 ms 74436 KB Output is correct
25 Correct 122 ms 74428 KB Output is correct
26 Correct 165 ms 72224 KB Output is correct
27 Correct 148 ms 77072 KB Output is correct
28 Correct 128 ms 74680 KB Output is correct
29 Correct 146 ms 77004 KB Output is correct
30 Correct 124 ms 74460 KB Output is correct
31 Correct 145 ms 77004 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 62044 KB Output is correct
2 Correct 14 ms 62552 KB Output is correct
3 Correct 14 ms 62168 KB Output is correct
4 Correct 13 ms 62188 KB Output is correct
5 Correct 15 ms 62300 KB Output is correct
6 Correct 14 ms 62300 KB Output is correct
7 Correct 12 ms 62040 KB Output is correct
8 Correct 12 ms 62044 KB Output is correct
9 Correct 14 ms 62300 KB Output is correct
10 Correct 13 ms 62096 KB Output is correct
11 Correct 14 ms 62300 KB Output is correct
12 Correct 14 ms 62112 KB Output is correct
13 Correct 13 ms 62300 KB Output is correct
14 Correct 14 ms 62300 KB Output is correct
15 Correct 14 ms 62296 KB Output is correct
16 Correct 228 ms 78564 KB Output is correct
17 Correct 573 ms 98252 KB Output is correct
18 Correct 52 ms 64852 KB Output is correct
19 Correct 152 ms 78924 KB Output is correct
20 Correct 542 ms 98108 KB Output is correct
21 Correct 270 ms 82552 KB Output is correct
22 Correct 237 ms 89420 KB Output is correct
23 Correct 541 ms 98244 KB Output is correct
24 Correct 593 ms 98008 KB Output is correct
25 Correct 527 ms 97808 KB Output is correct
26 Correct 146 ms 77764 KB Output is correct
27 Correct 160 ms 78676 KB Output is correct
28 Correct 150 ms 77812 KB Output is correct
29 Correct 149 ms 78276 KB Output is correct
30 Correct 145 ms 78788 KB Output is correct
31 Correct 12 ms 62040 KB Output is correct
32 Correct 12 ms 62044 KB Output is correct
33 Correct 12 ms 62044 KB Output is correct
34 Correct 12 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 12 ms 62192 KB Output is correct
38 Correct 14 ms 62040 KB Output is correct
39 Correct 12 ms 62152 KB Output is correct
40 Correct 13 ms 62044 KB Output is correct
41 Correct 281 ms 76828 KB Output is correct
42 Correct 497 ms 91380 KB Output is correct
43 Correct 469 ms 91388 KB Output is correct
44 Correct 152 ms 77000 KB Output is correct
45 Correct 499 ms 91724 KB Output is correct
46 Correct 471 ms 91712 KB Output is correct
47 Correct 465 ms 91672 KB Output is correct
48 Correct 474 ms 91728 KB Output is correct
49 Correct 485 ms 91532 KB Output is correct
50 Correct 477 ms 91580 KB Output is correct
51 Correct 477 ms 91732 KB Output is correct
52 Correct 496 ms 91672 KB Output is correct
53 Correct 502 ms 91880 KB Output is correct
54 Correct 498 ms 91636 KB Output is correct
55 Correct 477 ms 91380 KB Output is correct
56 Correct 514 ms 91620 KB Output is correct
57 Correct 481 ms 91612 KB Output is correct
58 Correct 492 ms 91460 KB Output is correct
59 Correct 143 ms 77064 KB Output is correct
60 Correct 499 ms 91592 KB Output is correct
61 Correct 353 ms 92036 KB Output is correct
62 Correct 116 ms 74436 KB Output is correct
63 Correct 179 ms 74440 KB Output is correct
64 Correct 116 ms 74436 KB Output is correct
65 Correct 122 ms 74428 KB Output is correct
66 Correct 165 ms 72224 KB Output is correct
67 Correct 148 ms 77072 KB Output is correct
68 Correct 128 ms 74680 KB Output is correct
69 Correct 146 ms 77004 KB Output is correct
70 Correct 124 ms 74460 KB Output is correct
71 Correct 145 ms 77004 KB Output is correct
72 Correct 313 ms 83436 KB Output is correct
73 Correct 544 ms 98124 KB Output is correct
74 Correct 529 ms 97992 KB Output is correct
75 Correct 535 ms 98160 KB Output is correct
76 Correct 526 ms 98264 KB Output is correct
77 Correct 530 ms 98252 KB Output is correct
78 Correct 533 ms 97980 KB Output is correct
79 Correct 547 ms 98104 KB Output is correct
80 Correct 592 ms 98404 KB Output is correct
81 Correct 504 ms 97996 KB Output is correct
82 Correct 561 ms 98280 KB Output is correct
83 Correct 548 ms 98060 KB Output is correct
84 Correct 522 ms 97796 KB Output is correct
85 Correct 516 ms 97584 KB Output is correct
86 Correct 530 ms 98048 KB Output is correct
87 Correct 507 ms 98012 KB Output is correct
88 Correct 542 ms 98252 KB Output is correct
89 Correct 261 ms 89472 KB Output is correct
90 Correct 525 ms 98020 KB Output is correct
91 Correct 419 ms 97304 KB Output is correct
92 Correct 149 ms 78804 KB Output is correct
93 Correct 272 ms 84336 KB Output is correct
94 Correct 145 ms 78192 KB Output is correct
95 Correct 145 ms 78280 KB Output is correct
96 Correct 225 ms 80104 KB Output is correct
97 Correct 225 ms 88248 KB Output is correct
98 Correct 146 ms 78100 KB Output is correct
99 Correct 250 ms 88156 KB Output is correct
100 Correct 154 ms 78016 KB Output is correct