| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 669443 | Bogdan1110 | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "dreaming.h"
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pqueue priority_queue
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair
using namespace std;
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
const double eps = 0.00000001;
const int NMAX = 2000010;
const ll inf = LLONG_MAX/3;
const ll modi = 998244353;
int D, maks, mx;
vector<pii>al[NMAX];
int visited[NMAX], dis[NMAX], vv[NMAX];
int maksd,poc;
vector<int>vis,nes;
set<int>vektor;
void izr() {
for (auto u : vis) {
u = dis[u];
maks = min(maks, u);
}
}
void dfs1(int node, int dist = 0) {
if (visited[node]) {
return;
}
vv[node] = 1;
vis.pb(node);
visited[node] =1;
if ( dist > maksd ) {
maksd = dist;
poc = node;
}
for (auto u : al[node] ) {
dfs1(u.fi, u.se + dist);
}
}
void dfs2(int node, int dist = 0) {
if (visited[node]) {
return;
}
vis.pb(node);
visited[node] =1;
dis[node] = max(dis[node], dist);
if ( dist > maksd ) {
maksd = dist;
poc = node;
}
for (auto u : al[node] ) {
dfs2(u.fi, u.se + dist);
}
}
void clrvis() {
for (auto u : vis) {
visited[u] = 0;
}
vis.clear();
}
void clrdis() {
for (auto u : vis) {
dis[u] = 0;
}
}
int travelTime(int n,int m,int l,int A[],int B[],int T[]) {
for (int i = 0 ; i < m; i++) {
al[A[i]].pb({B[i],T[i]});
al[B[i]].pb({A[i],T[i]});
}
vector<int>r;
for (int i = 0 ; i < n ; i++ ) {
if (!vv[i]) {
maksd = -1;
dfs1(i);
clrvis();
int poc1 = poc;
maksd = -1;
dfs1(poc);
clrdis();
clrvis();
int poc2 = poc;
D = maksd;
dfs2(poc1);
clrvis();
dfs2(poc2);
maks = INT_MAX;
izr();
clrdis();
//cout << D << ' ' << maks << endl;
r.pb(maks);
}
}
//for (auto u : r) cout << u << ' ';
sort(all(r));
int res = r[r.size()-1];
if ( r.size() == 1 ) {
return res;
}
if ( r.size() == 2 ) {
return res + r[0] + l;
}
res = max(res, res + r[r.size()-2] + l);
res = max(res , r[r.size()-2] + l + r[r.size()-3] + l);
return res;
}