| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 82371 |
2018-10-30T10:10:50 Z |
user202729 |
007 (CEOI14_007) |
C++17 |
|
641 ms |
17500 KB |
// https://oj.uz/problem/view/CEOI14_007
#include<iostream>
auto&I=std::cin;auto&O=std::cout;
#include<vector>
#include<queue>
std::vector<std::vector<int>> adjl;
int INF=2e9;
std::vector<int> minDistTo(int node){
std::vector<int> minDist(adjl.size(),INF);
std::queue<int> q;
q.push(node);minDist[node]=0;
while(!q.empty()){
node=q.front();q.pop();
for(int adj:adjl[node])
if(minDist[adj]==INF){
minDist[adj]=minDist[node]+1;
q.push(adj);
}
}
return minDist;
}
int main(){
int nnode,nedge,_007Start,nullStart,socket1,socket2;
I>>nnode>>nedge>>_007Start>>nullStart>>socket1>>socket2;
--_007Start;--nullStart;--socket1;--socket2;
adjl.resize(nnode);
for(int i=nedge;i-->0;){
int u,v;I>>u>>v;--u;--v;
adjl[u].push_back(v);
adjl[v].push_back(u);
}
auto minDist007=minDistTo(_007Start);
auto minDistNull=minDistTo(nullStart);
auto minDistS1=minDistTo(socket1);
auto minDistS2=minDistTo(socket2);
/// Return whether 007 can prevent Dr. De Referenced Nullpointer from pulling the plug of a server
auto check=[&](int breakfastTime){
if(minDistNull[socket1]<breakfastTime+minDist007[socket1]||
minDistNull[socket2]<breakfastTime+minDist007[socket2])return false;
else if(minDistNull[socket1]>breakfastTime+minDist007[socket1]||
minDistNull[socket2]>breakfastTime+minDist007[socket2])return true;
// otherwise, the distance of both person to each socket is equal
auto bestBranchPointValue=[&](std::vector<int> const& minDistNode){
// find max k such that there is a node with dist k from (node) and is on the min path from
// (node) to both sockets
int maxK=-1;
for(int n_=0;n_<nnode;++n_)
if(minDistNode[n_]+minDistS1[n_]==minDistNode[socket1]&&
minDistNode[n_]+minDistS2[n_]==minDistNode[socket2])
maxK=std::max(maxK,minDistNode[n_]);
return maxK;
};
if(bestBranchPointValue(minDistNull)>breakfastTime+bestBranchPointValue(minDist007))
return false;
else return true;
};
int ans=-1;
for(int i=1<<20;i;i>>=1){
ans+=i;
if(!check(ans))
ans-=i;
}
O<<ans<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
508 KB |
Output is correct |
| 3 |
Correct |
2 ms |
508 KB |
Output is correct |
| 4 |
Correct |
2 ms |
508 KB |
Output is correct |
| 5 |
Correct |
2 ms |
508 KB |
Output is correct |
| 6 |
Correct |
2 ms |
508 KB |
Output is correct |
| 7 |
Correct |
2 ms |
528 KB |
Output is correct |
| 8 |
Correct |
2 ms |
528 KB |
Output is correct |
| 9 |
Correct |
2 ms |
576 KB |
Output is correct |
| 10 |
Correct |
2 ms |
576 KB |
Output is correct |
| 11 |
Correct |
2 ms |
704 KB |
Output is correct |
| 12 |
Correct |
2 ms |
704 KB |
Output is correct |
| 13 |
Correct |
2 ms |
704 KB |
Output is correct |
| 14 |
Correct |
2 ms |
704 KB |
Output is correct |
| 15 |
Correct |
2 ms |
704 KB |
Output is correct |
| 16 |
Correct |
2 ms |
704 KB |
Output is correct |
| 17 |
Correct |
2 ms |
704 KB |
Output is correct |
| 18 |
Correct |
2 ms |
704 KB |
Output is correct |
| 19 |
Correct |
2 ms |
704 KB |
Output is correct |
| 20 |
Correct |
3 ms |
704 KB |
Output is correct |
| 21 |
Correct |
2 ms |
704 KB |
Output is correct |
| 22 |
Correct |
2 ms |
704 KB |
Output is correct |
| 23 |
Correct |
2 ms |
704 KB |
Output is correct |
| 24 |
Correct |
3 ms |
704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
3464 KB |
Output is correct |
| 2 |
Correct |
61 ms |
4764 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4764 KB |
Output is correct |
| 4 |
Correct |
66 ms |
4860 KB |
Output is correct |
| 5 |
Correct |
47 ms |
4860 KB |
Output is correct |
| 6 |
Correct |
47 ms |
4860 KB |
Output is correct |
| 7 |
Correct |
54 ms |
4860 KB |
Output is correct |
| 8 |
Correct |
55 ms |
4860 KB |
Output is correct |
| 9 |
Correct |
89 ms |
4860 KB |
Output is correct |
| 10 |
Correct |
409 ms |
9240 KB |
Output is correct |
| 11 |
Correct |
102 ms |
9240 KB |
Output is correct |
| 12 |
Correct |
153 ms |
9240 KB |
Output is correct |
| 13 |
Correct |
117 ms |
9240 KB |
Output is correct |
| 14 |
Correct |
102 ms |
9240 KB |
Output is correct |
| 15 |
Correct |
133 ms |
9240 KB |
Output is correct |
| 16 |
Correct |
173 ms |
9240 KB |
Output is correct |
| 17 |
Correct |
118 ms |
9240 KB |
Output is correct |
| 18 |
Correct |
133 ms |
9240 KB |
Output is correct |
| 19 |
Correct |
221 ms |
9596 KB |
Output is correct |
| 20 |
Correct |
447 ms |
12412 KB |
Output is correct |
| 21 |
Correct |
192 ms |
12412 KB |
Output is correct |
| 22 |
Correct |
172 ms |
12412 KB |
Output is correct |
| 23 |
Correct |
206 ms |
12412 KB |
Output is correct |
| 24 |
Correct |
190 ms |
12412 KB |
Output is correct |
| 25 |
Correct |
183 ms |
12412 KB |
Output is correct |
| 26 |
Correct |
168 ms |
12412 KB |
Output is correct |
| 27 |
Correct |
203 ms |
12412 KB |
Output is correct |
| 28 |
Correct |
236 ms |
12412 KB |
Output is correct |
| 29 |
Correct |
337 ms |
12412 KB |
Output is correct |
| 30 |
Correct |
506 ms |
13692 KB |
Output is correct |
| 31 |
Correct |
226 ms |
13692 KB |
Output is correct |
| 32 |
Correct |
211 ms |
13692 KB |
Output is correct |
| 33 |
Correct |
207 ms |
13692 KB |
Output is correct |
| 34 |
Correct |
241 ms |
13692 KB |
Output is correct |
| 35 |
Correct |
193 ms |
13692 KB |
Output is correct |
| 36 |
Correct |
211 ms |
13692 KB |
Output is correct |
| 37 |
Correct |
247 ms |
14260 KB |
Output is correct |
| 38 |
Correct |
242 ms |
14260 KB |
Output is correct |
| 39 |
Correct |
287 ms |
14260 KB |
Output is correct |
| 40 |
Correct |
420 ms |
15312 KB |
Output is correct |
| 41 |
Correct |
641 ms |
17500 KB |
Output is correct |
