| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 573861 | MohamedFaresNebili | 꿈 (IOI13_dreaming) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
/// #include "dreaming.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
const int oo = 1e18 + 7;
int res, par[100001], E[100001], D[100001];
vector<ii> adj[100001];
vector<int> S;
bool vis[100001];
int findSet(int v) {
if(par[v] == v) return v;
return par[v] = findSet(par[v]);
}
void unionSet(int u, int v, int L) {
u = findSet(u); v = findSet(v);
if(u == v) return;
if(max(E[u], E[v] + L) > max(E[v], E[u] + L)) swap(u, v);
res = max(res, E[u] + E[v] + L);
E[u] = max(E[u], E[v] + L);
par[v] = u;
}
void dfs(int v, int p, int dep) {
D[v] = dep; S.pb(v);
for(auto u : adj[v]) {
if(u.ff == p) continue;
dfs(u.ff, v, dep + u.ss);
}
}
void dfs(int v, int p, int dep, vector<int>& d) {
d[v] = dep;
for(auto u : adj[v]) {
if(u.ff == p) continue;
dfs(u.ff, v, dep + u.ss, d);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int l = 0; l < N; l++) par[l] = l;
for(int l = 0; l < M; l++) {
int U = A[l], V = B[l], W = T[l];
adj[U].pb({V, W}), adj[V].pb({U, W});
}
for(int l = 0; l < N; l++) {
if(vis[l]) continue;
dfs(l, l, 0);
int p = l;
for(auto u : S) {
if(D[u] <= D[p]) continue;
p = u;
}
vector<int> D1(N + 1, 0);
dfs(p, p, 0, D1); int to = p;
for(auto u : S) {
if(D1[u] <= D1[to]) continue;
to = u; res = max(res, D1[u]);
}
vector<int> D2(N + 1, 0); dfs(to, to, 0, D2);
int med = p, curr = 1e9 + 7;
for(auto u : S) {
if(D1[u] + D2[u] == D1[to]) {
if(max(D1[u], D2[u]) < curr)
med = u, curr = max(D1[u], D2[u]);
}
}
for(auto u : S) par[u] = med, vis[u] = 1;
E[med] = curr; S.clear();
}
for(int l = 1; l < N; l++)
unionSet(l - 1, l, L);
return res;
}