oj.uz

Submission #47726

# Submission time Handle Problem Language Result Execution time Memory
47726 2018-05-06T18:29:44 Z dqhungdl Evacuation plan (IZhO18_plan) C++17
100 / 100
 1221 ms 46536 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAX=17;
typedef pair<int,int> ii;
int n,m,k,T,d[100005],R[100005],S[100005],h[100005],P[100005][20],mind[100005][20];
vector<ii> Edge,g[100005],gg[100005];
set<ii> s;
 
bool cmp(ii x1,ii x2)
{
	return min(d[x1.first],d[x1.second])>min(d[x2.first],d[x2.second]);
}
 
int Find(int u)
{
	if(u==R[u])
		return u;
	return R[u]=Find(R[u]);
}
 
void Union(int u,int v)
{
	if(S[u]>S[v])
	{
		S[u]+=S[v];
		R[v]=u;
	}
	else
	{
		S[v]+=S[u];
		R[u]=v;
	}
}
 
void Enter()
{
	cin>>n>>m;
	int u,v,w;
	while(m--)
	{
		cin>>u>>v>>w;
		Edge.push_back(ii(u,v));
		g[u].push_back(ii(v,w));
		g[v].push_back(ii(u,w));
	}
	for(int i=1;i<=n;i++)
	{
		d[i]=1e9;
		R[i]=i;
	}
	cin>>k;
	while(k--)
	{
		cin>>u;
		s.insert(ii(0,u));
		d[u]=0;
	}
}
 
void BFS()
{
	while(s.size()>0)
	{
		int u=(*s.begin()).second;
		s.erase(s.begin());
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i].first;
			int w=g[u][i].second;
			if(d[v]>d[u]+w)
			{
				if(d[v]!=1e9)
					s.erase(s.find(ii(d[v],v)));
				d[v]=d[u]+w;
				s.insert(ii(d[v],v));
			}
		}
	}
}
 
void DFS(int u,int high)
{
	h[u]=high;
	for(int i=0;i<gg[u].size();i++)
	{
		int v=gg[u][i].first;
		int w=gg[u][i].second;
		if(h[v]==0)
		{
			P[v][0]=u;
			mind[v][0]=w;
			DFS(v,high+1);					
		}
	}
}
 
int LCA(int u,int v)
{
	int rs=1e9;
    for(int k=MAX;k>=0;k--)
        if(h[P[u][k]]>=h[v])
        {
        	rs=min(rs,mind[u][k]);
            u=P[u][k];         
        }
        else
        if(h[P[v][k]]>=h[u])
        {
        	rs=min(rs,mind[v][k]);
            v=P[v][k];
        }
    for(int k=MAX;k>=0;k--)
        if(P[u][k]!=P[v][k])
        {
        	rs=min(rs,mind[u][k]);
        	rs=min(rs,mind[v][k]);
            u=P[u][k];
            v=P[v][k];
        }
    while(u!=v)
    {
    	rs=min(rs,mind[u][0]);
        rs=min(rs,mind[v][0]);
        u=P[u][0];
        v=P[v][0];
    }
    return rs;
}
 
void InitTree()
{
	sort(Edge.begin(),Edge.end(),cmp);
	for(int i=0;i<Edge.size();i++)
	{
		int u=Edge[i].first;
		int v=Edge[i].second;
		int w=min(d[u],d[v]);
		if(Find(u)!=Find(v))
		{
			Union(Find(u),Find(v));
			gg[u].push_back(ii(v,w));
			gg[v].push_back(ii(u,w));
		}
	}
	DFS(1,1);
	for(int k=1;k<=MAX;k++)
    	for(int i=1;i<=n;i++)
    	{
			P[i][k]=P[P[i][k-1]][k-1];
			mind[i][k]=min(mind[i][k-1],mind[P[i][k-1]][k-1]);
    	}
}
 
void Query()
{
	cin>>T;
	int u,v;
	while(T--)
	{
		cin>>u>>v;
		cout<<LCA(u,v)<<"\n";
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	//freopen("TEST.INP","r",stdin);
	//freopen("TEST.OUT","w",stdout);
	Enter();
	BFS();
	InitTree();
	Query();
}

Compilation message

plan.cpp: In function 'void BFS()':
plan.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++)
               ~^~~~~~~~~~~~
plan.cpp: In function 'void DFS(int, int)':
plan.cpp:85:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<gg[u].size();i++)
              ~^~~~~~~~~~~~~
plan.cpp: In function 'void InitTree()':
plan.cpp:134:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<Edge.size();i++)
              ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 10 ms 5368 KB Output is correct
3 Correct 10 ms 5368 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 10 ms 5368 KB Output is correct
6 Correct 10 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5108 KB Output is correct
9 Correct 10 ms 5368 KB Output is correct
10 Correct 10 ms 5368 KB Output is correct
11 Correct 10 ms 5368 KB Output is correct
12 Correct 10 ms 5368 KB Output is correct
13 Correct 11 ms 5396 KB Output is correct
14 Correct 10 ms 5356 KB Output is correct
15 Correct 10 ms 5368 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 10 ms 5368 KB Output is correct
3 Correct 10 ms 5368 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 10 ms 5368 KB Output is correct
6 Correct 10 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5108 KB Output is correct
9 Correct 10 ms 5368 KB Output is correct
10 Correct 10 ms 5368 KB Output is correct
11 Correct 10 ms 5368 KB Output is correct
12 Correct 10 ms 5368 KB Output is correct
13 Correct 11 ms 5396 KB Output is correct
14 Correct 10 ms 5356 KB Output is correct
15 Correct 10 ms 5368 KB Output is correct
16 Correct 573 ms 25996 KB Output is correct
17 Correct 1117 ms 43392 KB Output is correct
18 Correct 84 ms 9556 KB Output is correct
19 Correct 513 ms 32412 KB Output is correct
20 Correct 1141 ms 43244 KB Output is correct
21 Correct 755 ms 33784 KB Output is correct
22 Correct 514 ms 34920 KB Output is correct
23 Correct 1133 ms 43172 KB Output is correct
24 Correct 1123 ms 43248 KB Output is correct
25 Correct 1205 ms 43128 KB Output is correct
26 Correct 509 ms 32196 KB Output is correct
27 Correct 512 ms 32300 KB Output is correct
28 Correct 502 ms 32220 KB Output is correct
29 Correct 521 ms 32184 KB Output is correct
30 Correct 509 ms 32372 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 33492 KB Output is correct
2 Correct 774 ms 42676 KB Output is correct
3 Correct 773 ms 42608 KB Output is correct
4 Correct 202 ms 32208 KB Output is correct
5 Correct 723 ms 42628 KB Output is correct
6 Correct 788 ms 42616 KB Output is correct
7 Correct 769 ms 43328 KB Output is correct
8 Correct 770 ms 43484 KB Output is correct
9 Correct 782 ms 43456 KB Output is correct
10 Correct 769 ms 43216 KB Output is correct
11 Correct 801 ms 43480 KB Output is correct
12 Correct 770 ms 44176 KB Output is correct
13 Correct 780 ms 44092 KB Output is correct
14 Correct 791 ms 44024 KB Output is correct
15 Correct 768 ms 44152 KB Output is correct
16 Correct 784 ms 44112 KB Output is correct
17 Correct 755 ms 44208 KB Output is correct
18 Correct 756 ms 44464 KB Output is correct
19 Correct 179 ms 34256 KB Output is correct
20 Correct 775 ms 43944 KB Output is correct
21 Correct 702 ms 44584 KB Output is correct
22 Correct 194 ms 32400 KB Output is correct
23 Correct 186 ms 31460 KB Output is correct
24 Correct 184 ms 32588 KB Output is correct
25 Correct 186 ms 32448 KB Output is correct
26 Correct 225 ms 31772 KB Output is correct
27 Correct 215 ms 34560 KB Output is correct
28 Correct 196 ms 32312 KB Output is correct
29 Correct 207 ms 33516 KB Output is correct
30 Correct 192 ms 32384 KB Output is correct
31 Correct 209 ms 33632 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 10 ms 5368 KB Output is correct
3 Correct 10 ms 5368 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 10 ms 5368 KB Output is correct
6 Correct 10 ms 5368 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 6 ms 5108 KB Output is correct
9 Correct 10 ms 5368 KB Output is correct
10 Correct 10 ms 5368 KB Output is correct
11 Correct 10 ms 5368 KB Output is correct
12 Correct 10 ms 5368 KB Output is correct
13 Correct 11 ms 5396 KB Output is correct
14 Correct 10 ms 5356 KB Output is correct
15 Correct 10 ms 5368 KB Output is correct
16 Correct 573 ms 25996 KB Output is correct
17 Correct 1117 ms 43392 KB Output is correct
18 Correct 84 ms 9556 KB Output is correct
19 Correct 513 ms 32412 KB Output is correct
20 Correct 1141 ms 43244 KB Output is correct
21 Correct 755 ms 33784 KB Output is correct
22 Correct 514 ms 34920 KB Output is correct
23 Correct 1133 ms 43172 KB Output is correct
24 Correct 1123 ms 43248 KB Output is correct
25 Correct 1205 ms 43128 KB Output is correct
26 Correct 509 ms 32196 KB Output is correct
27 Correct 512 ms 32300 KB Output is correct
28 Correct 502 ms 32220 KB Output is correct
29 Correct 521 ms 32184 KB Output is correct
30 Correct 509 ms 32372 KB Output is correct
31 Correct 6 ms 5112 KB Output is correct
32 Correct 6 ms 5112 KB Output is correct
33 Correct 6 ms 5112 KB Output is correct
34 Correct 6 ms 5112 KB Output is correct
35 Correct 6 ms 5112 KB Output is correct
36 Correct 6 ms 5112 KB Output is correct
37 Correct 6 ms 5112 KB Output is correct
38 Correct 6 ms 5116 KB Output is correct
39 Correct 6 ms 5112 KB Output is correct
40 Correct 6 ms 5112 KB Output is correct
41 Correct 368 ms 33492 KB Output is correct
42 Correct 774 ms 42676 KB Output is correct
43 Correct 773 ms 42608 KB Output is correct
44 Correct 202 ms 32208 KB Output is correct
45 Correct 723 ms 42628 KB Output is correct
46 Correct 788 ms 42616 KB Output is correct
47 Correct 769 ms 43328 KB Output is correct
48 Correct 770 ms 43484 KB Output is correct
49 Correct 782 ms 43456 KB Output is correct
50 Correct 769 ms 43216 KB Output is correct
51 Correct 801 ms 43480 KB Output is correct
52 Correct 770 ms 44176 KB Output is correct
53 Correct 780 ms 44092 KB Output is correct
54 Correct 791 ms 44024 KB Output is correct
55 Correct 768 ms 44152 KB Output is correct
56 Correct 784 ms 44112 KB Output is correct
57 Correct 755 ms 44208 KB Output is correct
58 Correct 756 ms 44464 KB Output is correct
59 Correct 179 ms 34256 KB Output is correct
60 Correct 775 ms 43944 KB Output is correct
61 Correct 702 ms 44584 KB Output is correct
62 Correct 194 ms 32400 KB Output is correct
63 Correct 186 ms 31460 KB Output is correct
64 Correct 184 ms 32588 KB Output is correct
65 Correct 186 ms 32448 KB Output is correct
66 Correct 225 ms 31772 KB Output is correct
67 Correct 215 ms 34560 KB Output is correct
68 Correct 196 ms 32312 KB Output is correct
69 Correct 207 ms 33516 KB Output is correct
70 Correct 192 ms 32384 KB Output is correct
71 Correct 209 ms 33632 KB Output is correct
72 Correct 712 ms 35228 KB Output is correct
73 Correct 1120 ms 44332 KB Output is correct
74 Correct 1168 ms 45008 KB Output is correct
75 Correct 1110 ms 44780 KB Output is correct
76 Correct 1111 ms 44480 KB Output is correct
77 Correct 1145 ms 44900 KB Output is correct
78 Correct 1221 ms 44496 KB Output is correct
79 Correct 1148 ms 44484 KB Output is correct
80 Correct 1131 ms 43536 KB Output is correct
81 Correct 1123 ms 43744 KB Output is correct
82 Correct 1131 ms 43508 KB Output is correct
83 Correct 1191 ms 43636 KB Output is correct
84 Correct 1155 ms 43720 KB Output is correct
85 Correct 1167 ms 43688 KB Output is correct
86 Correct 1113 ms 43692 KB Output is correct
87 Correct 1111 ms 43580 KB Output is correct
88 Correct 1109 ms 44644 KB Output is correct
89 Correct 593 ms 35852 KB Output is correct
90 Correct 1134 ms 46288 KB Output is correct
91 Correct 1040 ms 46536 KB Output is correct
92 Correct 522 ms 33756 KB Output is correct
93 Correct 569 ms 33396 KB Output is correct
94 Correct 527 ms 33544 KB Output is correct
95 Correct 526 ms 33552 KB Output is correct
96 Correct 580 ms 33240 KB Output is correct
97 Correct 630 ms 34268 KB Output is correct
98 Correct 521 ms 33312 KB Output is correct
99 Correct 658 ms 35304 KB Output is correct
100 Correct 530 ms 33348 KB Output is correct