oj.uz

답안 #507577

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
507577 2022-01-12T18:35:24 Z luka1234 Evacuation plan (IZhO18_plan) C++14
100 / 100
 1673 ms 63796 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n,m,q,rd;
vector<pair<ll,ll> > g[100001];
ll d[100001];
ll p[100001];
ll sz[100001];
pair<ll,ll> que[100001];
vector<pair<ll,ll> > ord; 
pair<ll,ll> saz[100001];
vector<ll> ms[100001];
bool check[100001];
void dijkstra(vector<ll> v){
	set<pair<ll,ll> > s;
	fill(d,d+n+1,1e9);
	for(ll k:v){
		d[k]=0;
		s.insert({0,k});
	}
	while(!s.empty()){
		ll gza=(*s.begin()).ff;
		ll ver=(*s.begin()).ss;
		s.erase(s.begin());
		for(pair<ll,ll> i:g[ver]){
			if(d[ver]+i.ss<d[i.ff]){
			    s.erase({d[i.ff],i.ff});
				d[i.ff]=d[ver]+i.ss;
				s.insert({d[i.ff],i.ff});
			}
		}
	}
}
void make_set(){
	for(ll k=1;k<=n;k++){
		p[k]=k;
		sz[k]=1;
	}
}
ll find_set(ll v){
    if(v==p[v])
       return v;
    return p[v]=find_set(p[v]);
}
void union_sets(ll a,ll b){
    a=find_set(a);
    b=find_set(b);
    if(a!=b){
        if(sz[a]<sz[b])
            swap(a,b);
        p[b]=a;
        sz[a]+=sz[b];
    }
}
void dsu(){
	make_set();
	ll v=1;
	for(pair<ll,ll> i:ord){
		for(pair<ll,ll> j:g[i.ss]){
			if(d[j.ff]>=d[i.ss])
			   union_sets(i.ss,j.ff);
		}
		for(ll j:ms[v]){
			ll fi=que[j].ff;
			ll se=que[j].ss;
			if(find_set(fi)==find_set(se)){
				check[j]=1;
			}
			else{
				check[j]=0;
			}
		}
		v++;
	}
}
int main(){
	cin>>n>>m;
	for(ll k=1;k<=m;k++){
		ll x,y,z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	cin>>rd;
	vector<ll> tx;
	for(ll k=1;k<=rd;k++){
		ll x;
		cin>>x;
		tx.push_back(x);
	}
	dijkstra(tx);
	for(ll k=1;k<=n;k++){
		ord.push_back({d[k],k});
	}
	sort(ord.begin(),ord.end());
	reverse(ord.begin(),ord.end());
	/*for(ll k=0;k<ord.size();k++)
	    cout<<ord[k].ff<<' '<<ord[k].ss<<"\n";
	cout<<"\n";*/
	cin>>q;
	for(ll k=1;k<=q;k++){
		saz[k].ff=1;
		saz[k].ss=n;
	}
	for(ll k=1;k<=q;k++){
		ll x,y;
		cin>>x>>y;
		que[k].ff=x;
		que[k].ss=y;
	}
	for(ll k=1;k<=20;k++){
		for(ll i=1;i<=n;i++)
		    ms[i].clear();
		fill(check,check+q+1,0);
		for(ll i=1;i<=q;i++){
			ll md=(saz[i].ff+saz[i].ss)/2;
			ms[md].push_back(i);
		}
		dsu();
		for(ll i=1;i<=q;i++){
			ll md=(saz[i].ff+saz[i].ss)/2;
			if(check[i]==1){
				saz[i].ss=md;
			}
			else{
				saz[i].ff=md+1;
			}
		}
	}
	for(ll k=1;k<=q;k++){
		ll ind=saz[k].ff;
		cout<<ord[ind-1].ff<<"\n";
	}
	return 0;
}

Compilation message

plan.cpp: In function 'void dijkstra(std::vector<long long int>)':
plan.cpp:24:6: warning: unused variable 'gza' [-Wunused-variable]
   24 |   ll gza=(*s.begin()).ff;
      |      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 6 ms 5196 KB Output is correct
11 Correct 6 ms 5196 KB Output is correct
12 Correct 5 ms 5196 KB Output is correct
13 Correct 5 ms 5196 KB Output is correct
14 Correct 5 ms 5196 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 632 ms 37140 KB Output is correct
17 Correct 1554 ms 63756 KB Output is correct
18 Correct 81 ms 10120 KB Output is correct
19 Correct 348 ms 37532 KB Output is correct
20 Correct 1576 ms 63460 KB Output is correct
21 Correct 840 ms 45108 KB Output is correct
22 Correct 499 ms 38404 KB Output is correct
23 Correct 1554 ms 63476 KB Output is correct
24 Correct 1526 ms 63600 KB Output is correct
25 Correct 1495 ms 63796 KB Output is correct
26 Correct 380 ms 37284 KB Output is correct
27 Correct 360 ms 36488 KB Output is correct
28 Correct 367 ms 37328 KB Output is correct
29 Correct 352 ms 36448 KB Output is correct
30 Correct 368 ms 37072 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 787 ms 24928 KB Output is correct
2 Correct 1344 ms 44312 KB Output is correct
3 Correct 1429 ms 44752 KB Output is correct
4 Correct 231 ms 15364 KB Output is correct
5 Correct 1350 ms 44656 KB Output is correct
6 Correct 1330 ms 44328 KB Output is correct
7 Correct 1329 ms 44412 KB Output is correct
8 Correct 1404 ms 43216 KB Output is correct
9 Correct 1302 ms 44780 KB Output is correct
10 Correct 1316 ms 44400 KB Output is correct
11 Correct 1301 ms 44824 KB Output is correct
12 Correct 1265 ms 44812 KB Output is correct
13 Correct 1316 ms 44648 KB Output is correct
14 Correct 1248 ms 44180 KB Output is correct
15 Correct 1276 ms 44324 KB Output is correct
16 Correct 1239 ms 43688 KB Output is correct
17 Correct 1269 ms 44688 KB Output is correct
18 Correct 1255 ms 44984 KB Output is correct
19 Correct 223 ms 15368 KB Output is correct
20 Correct 1238 ms 43988 KB Output is correct
21 Correct 1045 ms 45800 KB Output is correct
22 Correct 277 ms 21508 KB Output is correct
23 Correct 278 ms 15720 KB Output is correct
24 Correct 285 ms 21364 KB Output is correct
25 Correct 266 ms 19952 KB Output is correct
26 Correct 369 ms 16056 KB Output is correct
27 Correct 229 ms 15364 KB Output is correct
28 Correct 254 ms 21476 KB Output is correct
29 Correct 224 ms 15288 KB Output is correct
30 Correct 287 ms 21532 KB Output is correct
31 Correct 212 ms 15288 KB Output is correct

Subtask #5
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5196 KB Output is correct
6 Correct 5 ms 5196 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 2 ms 4940 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 6 ms 5196 KB Output is correct
11 Correct 6 ms 5196 KB Output is correct
12 Correct 5 ms 5196 KB Output is correct
13 Correct 5 ms 5196 KB Output is correct
14 Correct 5 ms 5196 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 632 ms 37140 KB Output is correct
17 Correct 1554 ms 63756 KB Output is correct
18 Correct 81 ms 10120 KB Output is correct
19 Correct 348 ms 37532 KB Output is correct
20 Correct 1576 ms 63460 KB Output is correct
21 Correct 840 ms 45108 KB Output is correct
22 Correct 499 ms 38404 KB Output is correct
23 Correct 1554 ms 63476 KB Output is correct
24 Correct 1526 ms 63600 KB Output is correct
25 Correct 1495 ms 63796 KB Output is correct
26 Correct 380 ms 37284 KB Output is correct
27 Correct 360 ms 36488 KB Output is correct
28 Correct 367 ms 37328 KB Output is correct
29 Correct 352 ms 36448 KB Output is correct
30 Correct 368 ms 37072 KB Output is correct
31 Correct 3 ms 4940 KB Output is correct
32 Correct 2 ms 4940 KB Output is correct
33 Correct 3 ms 5028 KB Output is correct
34 Correct 4 ms 4940 KB Output is correct
35 Correct 4 ms 4940 KB Output is correct
36 Correct 3 ms 4940 KB Output is correct
37 Correct 3 ms 5008 KB Output is correct
38 Correct 3 ms 5016 KB Output is correct
39 Correct 3 ms 4940 KB Output is correct
40 Correct 3 ms 4940 KB Output is correct
41 Correct 787 ms 24928 KB Output is correct
42 Correct 1344 ms 44312 KB Output is correct
43 Correct 1429 ms 44752 KB Output is correct
44 Correct 231 ms 15364 KB Output is correct
45 Correct 1350 ms 44656 KB Output is correct
46 Correct 1330 ms 44328 KB Output is correct
47 Correct 1329 ms 44412 KB Output is correct
48 Correct 1404 ms 43216 KB Output is correct
49 Correct 1302 ms 44780 KB Output is correct
50 Correct 1316 ms 44400 KB Output is correct
51 Correct 1301 ms 44824 KB Output is correct
52 Correct 1265 ms 44812 KB Output is correct
53 Correct 1316 ms 44648 KB Output is correct
54 Correct 1248 ms 44180 KB Output is correct
55 Correct 1276 ms 44324 KB Output is correct
56 Correct 1239 ms 43688 KB Output is correct
57 Correct 1269 ms 44688 KB Output is correct
58 Correct 1255 ms 44984 KB Output is correct
59 Correct 223 ms 15368 KB Output is correct
60 Correct 1238 ms 43988 KB Output is correct
61 Correct 1045 ms 45800 KB Output is correct
62 Correct 277 ms 21508 KB Output is correct
63 Correct 278 ms 15720 KB Output is correct
64 Correct 285 ms 21364 KB Output is correct
65 Correct 266 ms 19952 KB Output is correct
66 Correct 369 ms 16056 KB Output is correct
67 Correct 229 ms 15364 KB Output is correct
68 Correct 254 ms 21476 KB Output is correct
69 Correct 224 ms 15288 KB Output is correct
70 Correct 287 ms 21532 KB Output is correct
71 Correct 212 ms 15288 KB Output is correct
72 Correct 1018 ms 44952 KB Output is correct
73 Correct 1513 ms 63416 KB Output is correct
74 Correct 1591 ms 63448 KB Output is correct
75 Correct 1572 ms 63596 KB Output is correct
76 Correct 1673 ms 63280 KB Output is correct
77 Correct 1637 ms 63680 KB Output is correct
78 Correct 1559 ms 63408 KB Output is correct
79 Correct 1587 ms 63336 KB Output is correct
80 Correct 1591 ms 63600 KB Output is correct
81 Correct 1611 ms 63432 KB Output is correct
82 Correct 1567 ms 63628 KB Output is correct
83 Correct 1573 ms 63696 KB Output is correct
84 Correct 1565 ms 63284 KB Output is correct
85 Correct 1554 ms 63484 KB Output is correct
86 Correct 1639 ms 63396 KB Output is correct
87 Correct 1584 ms 63408 KB Output is correct
88 Correct 1611 ms 63488 KB Output is correct
89 Correct 491 ms 39120 KB Output is correct
90 Correct 1569 ms 63432 KB Output is correct
91 Correct 1237 ms 63776 KB Output is correct
92 Correct 337 ms 36472 KB Output is correct
93 Correct 462 ms 36204 KB Output is correct
94 Correct 358 ms 36436 KB Output is correct
95 Correct 350 ms 36488 KB Output is correct
96 Correct 508 ms 34304 KB Output is correct
97 Correct 511 ms 37020 KB Output is correct
98 Correct 387 ms 36224 KB Output is correct
99 Correct 482 ms 36980 KB Output is correct
100 Correct 360 ms 35276 KB Output is correct