Submission #940201

#TimeUsernameProblemLanguageResultExecution timeMemory
940201mansurDreaming (IOI13_dreaming)C++17
18 / 100
52 ms40104 KiB
#include<bits/stdc++.h> #include "dreaming.h" using namespace std; #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define sz(a) (int)a.size() #define s second #define f first using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; const int inf = 1e9, N = 1e6; int travelTime2(int n, int l, vector<int> s) { //cout << n << '\n'; //for (int x: s) cout << x << ' '; //cout << '\n'; if (n == 1) return 0; if (n == 2) { if (sz(s)) return s[0]; return l; } s.push_back(0); s.push_back(0); s.push_back(0); sort(rall(s)); return max(s[0] + s[1] + l, s[1] + s[2] + 2 * l); } vector<int> d0(N, inf), d1(N, inf); vector<pii> g[N]; int val; int calc(int x, int n) { set<pii> s; vector<int> h; d0[x] = 0; s.insert({0, x}); int a = x; while (sz(s)) { x = (*s.begin()).s; if (d0[x] > d0[a]) a = x; h.push_back(x); s.erase(s.begin()); for (auto [to, w]: g[x]) { if (d0[to] <= d0[x] + w) continue; s.erase({d0[to], to}); d0[to] = d0[x] + w; s.insert({d0[to], to}); } } d1[a] = 0; s.insert({0, a}); int b = a; while (sz(s)) { x = (*s.begin()).s; if (d1[x] > d1[b]) b = x; s.erase(s.begin()); for (auto [to, w]: g[x]) { if (d1[to] <= d1[x] + w) continue; s.erase({d1[to], to}); d1[to] = d1[x] + w; s.insert({d1[to], to}); } } val = max(val, d1[b]); for (int v: h) d0[v] = inf; d0[b] = 0; s.insert({0, b}); while (sz(s)) { x = (*s.begin()).s; s.erase(s.begin()); for (auto [to, w]: g[x]) { if (d0[to] <= d0[x] + w) continue; s.erase({d0[to], to}); d0[to] = d0[x] + w; s.insert({d0[to], to}); } } int ans = inf; for (int v: h) { x = max(d0[v], d1[v]); ans = min(ans, x); d0[v] = d1[v] = inf; } return ans; } int p[N], sz[N]; int get(int x) { if (p[x] == x) return x; return p[x] = get(p[x]); } void unite(int a, int b) { a = get(a), b = get(b); if (a == b) return; if (sz[a] > sz[b]) swap(a, b); p[a] = b; sz[b] += sz[a]; } int travelTime(int n, int m, int l, int a[], int b[], int c[]) { for (int i = 0; i < n; i++) p[i] = i, sz[i] = 1; for (int i = 0; i < m; i++) { g[a[i]].push_back({b[i], c[i]}); g[b[i]].push_back({a[i], c[i]}); unite(a[i], b[i]); } vector<int> s; int cnt = 0; for (int i = 0; i < n; i++) { if (i == get(i)) cnt++; if (i == get(i) && sz[i] > 1) s.push_back(calc(i, n)), cnt++; } return max(val, travelTime2(cnt, l, s)); } #ifdef M main() { //freopen("rsq.in", "r", stdin); //freopen("rsq.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); int n, m, l; cin >> n >> m >> l; int a[m], b[m], c[m]; for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i]; cout << travelTime(n, m, l, a, b, c); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...