| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 115290 | suzy | Dreaming (IOI13_dreaming) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
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];
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) {
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) {
memset(d,-1,sizeof(d));
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);
}
vector<int> rt;
for(int i=1;i<=n;i++) if(!vis[i]) {
rt.push_back(i);
dfs(-1,i);
}
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());
return v.back()+v[v.size()-2];
}