| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 255428 |
2020-08-01T00:49:16 Z |
babo |
Dreaming (IOI13_dreaming) |
C++14 |
|
90 ms |
23928 KB |
#include <bits/stdc++.h>
#include "dreaming.h"
#define LL long long
using namespace std;
vector<LL>v[100010],t[100010];
LL n,len;
LL diam;
multiset<LL>rad;
LL chk[100010];
LL ord[100010],ordend[100010],ordtop;
LL max2(LL a,LL b,LL c){
if(a<=b&&a<=c) return b+c;
if(b<=c&&b<=a) return c+a;
if(c<=a&&c<=b) return a+b;
}
struct S{
LL ma1,ma1d,ma2,ma2d;
S(){
ma1=ma1d=ma2=ma2d=0;
}
void insert(LL dist,LL loc){
if(dist>=ma1)
{
ma2=ma1;
ma2d=ma1d;
ma1=dist;
ma1d=loc;
}
else if(dist>=ma2)
{
ma2=dist;
ma2d=loc;
}
}
}S[100010];
void dfs(LL x,LL bu){
ordtop++;
ord[x]=ordtop;
LL i;
S[x].insert(0,x);
for(i=0;i<v[x].size();i++)
{
if(v[x][i]!=bu)
{
chk[v[x][i]]=1;
dfs(v[x][i],x);
S[x].insert(S[v[x][i]].ma1+t[x][i],S[v[x][i]].ma1d);
}
}
diam=max(diam,S[x].ma1+S[x].ma2);
ordend[x]=ordtop;
}
LL dfs2(LL x,LL bu,LL give){
LL i,ret=max2(give,S[x].ma1,S[x].ma2);
for(i=0;i<v[x].size();i++)
{
if(v[x][i]!=bu)
{
if(ord[v[x][i]]<=ord[S[x].ma1d]&&ord[S[x].ma1d]<=ordend[v[x][i]])
{
if(S[x].ma2d)
ret=min(ret,dfs2(v[x][i],x,max(give+t[x][i],S[x].ma2)));
else ret=min(ret,dfs2(v[x][i],x,give+t[x][i]));
}
else
ret=min(ret,dfs2(v[x][i],x,max(give+t[x][i],S[x].ma1)));
}
}
return ret;
}
void tree(LL x){
chk[x]=1;
dfs(x,-1);
rad.insert(dfs2(x,-1,0));
}
int travelTime(int N,int M,int l,int A[],int B[],int T[]){
LL i;
n=N,len=l;
for(i=0;i<M;i++)
{
v[A[i]].push_back(B[i]);
v[B[i]].push_back(A[i]);
t[A[i]].push_back(T[i]);
t[B[i]].push_back(T[i]);
}
for(i=0;i<N;i++)
{
if(!chk[i])
tree(i);
}
if(rad.size()==1) return (int)diam;
else return max((int)diam,(int)(len+*prev(rad.end())+*prev(prev((rad.end())))));
}
Compilation message
dreaming.cpp: In function 'void dfs(long long int, long long int)':
dreaming.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
dreaming.cpp: In function 'long long int dfs2(long long int, long long int, long long int)':
dreaming.cpp:62:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
dreaming.cpp: In function 'long long int max2(long long int, long long int, long long int)':
dreaming.cpp:19:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
18040 KB |
Output is correct |
| 2 |
Incorrect |
52 ms |
18088 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
23928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
