| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 115294 |
2019-06-06T16:28:29 Z |
suzy |
Dreaming (IOI13_dreaming) |
C++17 |
|
0 ms |
0 KB |
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include "dreaming.h"
using namespace std;
class e {
public:
int v, w;
e(int v, int w)
:v(v),w(w)
{}
};
vector<e> con[100001];
int n, m, l, d[100001];
bool vis[100001];
vector<int> comp[100001];
int k;
int solve(int pre, int u, int up) {
int mx1=up, mx2=-1, v1=-1, v2=-1;
for(int i=0;i<con[u].size();i++) {
int v=con[u][i].v, w=con[u][i].w;
if(pre==v) continue;
if(d[v]+w>=mx1) {
mx2=mx1;
v2=v1;
mx1=d[v]+w;
v1=v;
} else if(d[v]+w>mx2) {
mx2=d[v]+w;
v2=v;
}
}
int ret=mx1;
for(int i=0;i<con[u].size();i++) {
int v=con[u][i].v, w=con[u][i].w;
if(pre==v) continue;
if(v==v1) ret=min(ret,solve(u,v,mx2+w));
else ret=min(ret,solve(u,v,mx1+w));
}
return ret;
}
void dfs(int pre, int u) {
comp[k].push_back(u);
vis[u]=true;
for(int i=0;i<con[u].size();i++) {
int v=con[u][i].v, w=con[u][i].w;
if(pre==v) continue;
dfs(u,v);
d[u]=max(d[u],d[v]+w);
}
}
int dia(int u, bool fst, int c) {
if(c<0) memset(d,-1,sizeof(d));
else {
for(int i=0;i<comp[c].size();i++)
d[comp[c][i]]=-1;
}
queue<int> q;
q.push(u);
d[u]=0;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=0;i<con[u].size();i++) {
int v=con[u][i].v, w=con[u][i].w;
if(d[v]<0) {
d[v]=d[u]+w;
q.push(v);
}
}
}
int mx=-1, tar;
for(int i=1;i<=n;i++) {
if(d[i]>mx) {
mx=d[i]; tar=i;
}
}
if(fst) return dia(tar,false);
else return mx;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N; m=M; l=L;
for(int i=0;i<m;i++) {
int u, v, w;
u=A[i]; v=B[i]; w=T[i];
u++; v++;
con[u].push_back(e(v,w));
con[v].push_back(e(u,w));
}
if(m==n-1) {
return dia(1,true,-1);
}
vector<int> rt;
for(int i=1;i<=n;i++) if(!vis[i]) {
rt.push_back(i);
dfs(-1,i);
k++;
}
vector<int> v;
for(int i=0;i<rt.size();i++)
v.push_back(solve(-1,rt[i],0));
sort(v.begin(),v.end());
for(int i=0;i<v.size()-1;i++) v[i]+=l;
sort(v.begin(),v.end());
int ret=v.back()+v[v.size()-2];
for(int i=0;i<rt.size();i++)
ret=max(ret,dia(rt[i],true,i));
return ret;
}
Compilation message
dreaming.cpp: In function 'int solve(int, int, int)':
dreaming.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<con[u].size();i++) {
~^~~~~~~~~~~~~~
dreaming.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<con[u].size();i++) {
~^~~~~~~~~~~~~~
dreaming.cpp:25:29: warning: variable 'v2' set but not used [-Wunused-but-set-variable]
int mx1=up, mx2=-1, v1=-1, v2=-1;
^~
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<con[u].size();i++) {
~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int dia(int, bool, int)':
dreaming.cpp:63:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<comp[c].size();i++)
~^~~~~~~~~~~~~~~
dreaming.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<con[u].size();i++) {
~^~~~~~~~~~~~~~
dreaming.cpp:86:30: error: too few arguments to function 'int dia(int, bool, int)'
if(fst) return dia(tar,false);
^
dreaming.cpp:60:5: note: declared here
int dia(int u, bool fst, int c) {
^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<rt.size();i++)
~^~~~~~~~~~
dreaming.cpp:112:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size()-1;i++) v[i]+=l;
~^~~~~~~~~~~
dreaming.cpp:115:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<rt.size();i++)
~^~~~~~~~~~
