oj.uz

Submission #342262

# Submission time Handle Problem Language Result Execution time Memory
342262 2021-01-01T16:57:53 Z ogibogi2004 Evacuation plan (IZhO18_plan) C++14
100 / 100
 871 ms 48712 KB 
#include<bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define fi first
#define se second
const int MAXN=1e5+6;
const int MAXM=5e5+6;
const int INF=2e9;
vector<pair<int,int> >g[MAXN];
struct edge
{
	int u,v;
	int w;
	bool operator<(edge const& other)const
	{
		return w>other.w;
	}
}e[MAXM];
int n,m,k;
int d[MAXN];
vector<int>q;
int l[MAXN],r[MAXN];
int s[MAXN],t[MAXN];
int par[MAXN],sz[MAXN];
bool used[MAXN];
vector<int>to_check[MAXM];
void dijkstra()
{
	priority_queue<pp,vector<pp>,greater<pp> >pq;
	for(auto xd:q)
	{
		pq.push({0,xd});
		d[xd]=0;
	}
	while(!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		if(used[u])continue;
		used[u]=1;
		for(auto v:g[u])
		{
			if(d[u]+v.second<d[v.first])
			{
				d[v.first]=v.second+d[u];
				pq.push({d[v.first],v.first});
			}
		}
	}
}
int getRoot(int u)
{
	if(u==par[u])return u;
	return par[u]=getRoot(par[u]);
}
void join(int u,int v)
{
	if(sz[u]>sz[v])
	{
		sz[u]+=sz[v];
		par[v]=u;
	}
	else
	{
		sz[v]+=sz[u];
		par[u]=v;
	}
}
void add_edge(edge eksdi)
{
	int u=getRoot(eksdi.u);
	int v=getRoot(eksdi.v);
	if(u!=v)join(u,v);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<m;++i)
	{
		int w;
		cin>>e[i].u>>e[i].v>>w;
		g[e[i].u].push_back({e[i].v,w});
		g[e[i].v].push_back({e[i].u,w});
	}
	for(int i=1;i<=n;++i)
	{
		d[i]=INF;
	}
	cin>>k;
	for(int i=1;i<=k;++i)
	{
		int x;
		cin>>x;
		q.push_back(x);
	}
	dijkstra();
	for(int i=0;i<m;++i)
	{
		e[i].w=min(d[e[i].v],d[e[i].u]);
	}
	sort(e,e+m);
	cin>>k;
	for(int i=1;i<=k;++i)
	{
		l[i]=0;r[i]=m-1;
		cin>>s[i]>>t[i];
	}
	for(int step=0;step<20;++step)
	{
		for(int i=1;i<=k;++i)
		{
			if(l[i]==r[i])continue;
			int mid=(l[i]+r[i])/2;
			to_check[mid].emplace_back(i);
		}
		for(int i=1;i<=n;++i)
		{
			par[i]=i;sz[i]=1;
		}
		for(int i=0;i<m;++i)
		{
			add_edge(e[i]);
			for(auto xd:to_check[i])
			{
				int u=getRoot(s[xd]);
				int v=getRoot(t[xd]);
				if(u==v)r[xd]=i;
				else l[xd]=i+1;
			}
			to_check[i].clear();
		}
	}
	for(int i=1;i<=k;++i)
	{
		cout<<e[l[i]].w<<"\n";
	}
return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7 
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 16 ms 14572 KB Output is correct
3 Correct 10 ms 14572 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 11 ms 14572 KB Output is correct
6 Correct 12 ms 14572 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14572 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 10 ms 14572 KB Output is correct
12 Correct 13 ms 14572 KB Output is correct
13 Correct 11 ms 14572 KB Output is correct
14 Correct 13 ms 14572 KB Output is correct
15 Correct 13 ms 14572 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 16 ms 14572 KB Output is correct
3 Correct 10 ms 14572 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 11 ms 14572 KB Output is correct
6 Correct 12 ms 14572 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14572 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 10 ms 14572 KB Output is correct
12 Correct 13 ms 14572 KB Output is correct
13 Correct 11 ms 14572 KB Output is correct
14 Correct 13 ms 14572 KB Output is correct
15 Correct 13 ms 14572 KB Output is correct
16 Correct 312 ms 31928 KB Output is correct
17 Correct 845 ms 48552 KB Output is correct
18 Correct 58 ms 17680 KB Output is correct
19 Correct 299 ms 32976 KB Output is correct
20 Correct 833 ms 48712 KB Output is correct
21 Correct 490 ms 37300 KB Output is correct
22 Correct 258 ms 32612 KB Output is correct
23 Correct 871 ms 48592 KB Output is correct
24 Correct 847 ms 48532 KB Output is correct
25 Correct 849 ms 48408 KB Output is correct
26 Correct 293 ms 32728 KB Output is correct
27 Correct 292 ms 32720 KB Output is correct
28 Correct 297 ms 32720 KB Output is correct
29 Correct 284 ms 32820 KB Output is correct
30 Correct 289 ms 32952 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 24816 KB Output is correct
2 Correct 628 ms 36072 KB Output is correct
3 Correct 652 ms 36072 KB Output is correct
4 Correct 120 ms 20076 KB Output is correct
5 Correct 608 ms 36012 KB Output is correct
6 Correct 671 ms 35984 KB Output is correct
7 Correct 639 ms 36072 KB Output is correct
8 Correct 610 ms 36012 KB Output is correct
9 Correct 746 ms 35952 KB Output is correct
10 Correct 637 ms 36164 KB Output is correct
11 Correct 687 ms 36068 KB Output is correct
12 Correct 601 ms 35948 KB Output is correct
13 Correct 610 ms 35996 KB Output is correct
14 Correct 625 ms 36104 KB Output is correct
15 Correct 597 ms 37088 KB Output is correct
16 Correct 641 ms 35984 KB Output is correct
17 Correct 596 ms 35944 KB Output is correct
18 Correct 617 ms 36200 KB Output is correct
19 Correct 118 ms 20076 KB Output is correct
20 Correct 663 ms 36072 KB Output is correct
21 Correct 592 ms 36200 KB Output is correct
22 Correct 152 ms 21472 KB Output is correct
23 Correct 151 ms 20588 KB Output is correct
24 Correct 167 ms 21600 KB Output is correct
25 Correct 133 ms 21472 KB Output is correct
26 Correct 161 ms 20776 KB Output is correct
27 Correct 146 ms 20076 KB Output is correct
28 Correct 144 ms 21600 KB Output is correct
29 Correct 118 ms 20064 KB Output is correct
30 Correct 161 ms 21728 KB Output is correct
31 Correct 119 ms 20076 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 16 ms 14572 KB Output is correct
3 Correct 10 ms 14572 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 11 ms 14572 KB Output is correct
6 Correct 12 ms 14572 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14572 KB Output is correct
10 Correct 11 ms 14572 KB Output is correct
11 Correct 10 ms 14572 KB Output is correct
12 Correct 13 ms 14572 KB Output is correct
13 Correct 11 ms 14572 KB Output is correct
14 Correct 13 ms 14572 KB Output is correct
15 Correct 13 ms 14572 KB Output is correct
16 Correct 312 ms 31928 KB Output is correct
17 Correct 845 ms 48552 KB Output is correct
18 Correct 58 ms 17680 KB Output is correct
19 Correct 299 ms 32976 KB Output is correct
20 Correct 833 ms 48712 KB Output is correct
21 Correct 490 ms 37300 KB Output is correct
22 Correct 258 ms 32612 KB Output is correct
23 Correct 871 ms 48592 KB Output is correct
24 Correct 847 ms 48532 KB Output is correct
25 Correct 849 ms 48408 KB Output is correct
26 Correct 293 ms 32728 KB Output is correct
27 Correct 292 ms 32720 KB Output is correct
28 Correct 297 ms 32720 KB Output is correct
29 Correct 284 ms 32820 KB Output is correct
30 Correct 289 ms 32952 KB Output is correct
31 Correct 10 ms 14444 KB Output is correct
32 Correct 9 ms 14444 KB Output is correct
33 Correct 12 ms 14444 KB Output is correct
34 Correct 10 ms 14444 KB Output is correct
35 Correct 10 ms 14444 KB Output is correct
36 Correct 10 ms 14444 KB Output is correct
37 Correct 12 ms 14496 KB Output is correct
38 Correct 9 ms 14592 KB Output is correct
39 Correct 9 ms 14444 KB Output is correct
40 Correct 11 ms 14444 KB Output is correct
41 Correct 313 ms 24816 KB Output is correct
42 Correct 628 ms 36072 KB Output is correct
43 Correct 652 ms 36072 KB Output is correct
44 Correct 120 ms 20076 KB Output is correct
45 Correct 608 ms 36012 KB Output is correct
46 Correct 671 ms 35984 KB Output is correct
47 Correct 639 ms 36072 KB Output is correct
48 Correct 610 ms 36012 KB Output is correct
49 Correct 746 ms 35952 KB Output is correct
50 Correct 637 ms 36164 KB Output is correct
51 Correct 687 ms 36068 KB Output is correct
52 Correct 601 ms 35948 KB Output is correct
53 Correct 610 ms 35996 KB Output is correct
54 Correct 625 ms 36104 KB Output is correct
55 Correct 597 ms 37088 KB Output is correct
56 Correct 641 ms 35984 KB Output is correct
57 Correct 596 ms 35944 KB Output is correct
58 Correct 617 ms 36200 KB Output is correct
59 Correct 118 ms 20076 KB Output is correct
60 Correct 663 ms 36072 KB Output is correct
61 Correct 592 ms 36200 KB Output is correct
62 Correct 152 ms 21472 KB Output is correct
63 Correct 151 ms 20588 KB Output is correct
64 Correct 167 ms 21600 KB Output is correct
65 Correct 133 ms 21472 KB Output is correct
66 Correct 161 ms 20776 KB Output is correct
67 Correct 146 ms 20076 KB Output is correct
68 Correct 144 ms 21600 KB Output is correct
69 Correct 118 ms 20064 KB Output is correct
70 Correct 161 ms 21728 KB Output is correct
71 Correct 119 ms 20076 KB Output is correct
72 Correct 482 ms 36788 KB Output is correct
73 Correct 853 ms 48536 KB Output is correct
74 Correct 865 ms 48648 KB Output is correct
75 Correct 842 ms 48516 KB Output is correct
76 Correct 845 ms 48568 KB Output is correct
77 Correct 854 ms 48556 KB Output is correct
78 Correct 815 ms 48392 KB Output is correct
79 Correct 838 ms 48516 KB Output is correct
80 Correct 849 ms 48516 KB Output is correct
81 Correct 829 ms 48516 KB Output is correct
82 Correct 818 ms 48520 KB Output is correct
83 Correct 824 ms 48604 KB Output is correct
84 Correct 834 ms 48444 KB Output is correct
85 Correct 834 ms 48416 KB Output is correct
86 Correct 822 ms 48520 KB Output is correct
87 Correct 831 ms 48520 KB Output is correct
88 Correct 816 ms 48648 KB Output is correct
89 Correct 254 ms 32868 KB Output is correct
90 Correct 827 ms 48520 KB Output is correct
91 Correct 765 ms 48044 KB Output is correct
92 Correct 271 ms 32964 KB Output is correct
93 Correct 264 ms 31332 KB Output is correct
94 Correct 271 ms 32728 KB Output is correct
95 Correct 275 ms 32976 KB Output is correct
96 Correct 277 ms 29596 KB Output is correct
97 Correct 231 ms 31076 KB Output is correct
98 Correct 279 ms 32860 KB Output is correct
99 Correct 228 ms 31076 KB Output is correct
100 Correct 284 ms 32960 KB Output is correct