Submission #336622

#TimeUsernameProblemLanguageResultExecution timeMemory
336622arwaeystoamnegDreaming (IOI13_dreaming)C++17
18 / 100
97 ms20460 KiB
#include "dreaming.h" /* ID: awesome35 LANG: C++14 TASK: vans */ #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> #include<unordered_set> #include<unordered_map> #include<chrono> using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pair<int, int>> vpi; typedef vector<pair<ll, ll>> vpll; #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define trav(a,x) for (auto& a: x) #define pb push_back #define mp make_pair #define rsz resize #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define f first #define s second #define cont continue #define endl '\n' #define ednl '\n' #define test int testc;cin>>testc;while(testc--) #define pr(a, b) trav(x,a)cerr << x << b; cerr << endl; #define message cout << "My name's Ozymandias, king of kings: look on my works, ye mighty and despair!" <<endl; const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!! const ll linf = 4000000000000000000LL; const ll inf = 1000000007;//998244353 const ld pi = 3.1415926535; void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; } }void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; } int n, m, l, maxdia; vector<vpi>adj; vi depth, parents, type; int cur; void depth_(int i, int p) { parents[i] = p; depth[i] = 0, type[i] = cur; trav(x, adj[i]) { if (x.f != p) { depth_(x.f, i); depth[i] = max(depth[i], depth[x.f] + x.s); } } } vi up; void up_(int i, int p) { up[i] = max(0, up[i]); multiset<int, greater<int>>t = { up[i] }; trav(x, adj[i]) { if (x.f != p) { t.insert(x.s + depth[x.f]); } } trav(x, adj[i]) { if (x.f != p) { t.erase(t.find(x.s + depth[x.f])); up[x.f] = x.s + *t.begin(); t.insert(x.s + depth[x.f]); } } trav(x, adj[i]) { if (x.f != p) { up_(x.f, i); } } } int travelTime(int a, int b, int c, int* d, int* e, int* f) { n = a; m = b; l = c; adj.rsz(n); F0R(i, m) { adj[d[i]].pb({ e[i],f[i] }); adj[e[i]].pb({ d[i],f[i] }); }/* if (n == 1) { return 0; } if (n == 2) { return m == 1 ? adj[0][0].s : l; }*/ depth.rsz(n, -1); parents.rsz(n); type.rsz(n); F0R(i, n) { if (depth[i] == -1)depth_(i, -1), cur++; } F0R(i, n) { int a = 0, b = 0; trav(x, adj[i]) { if (x.f != parents[i]) { if (a == 0)a = depth[x.f] + x.s; else if (b == 0) { if (a > depth[x.f] + x.s) b = depth[x.f] + x.s; else { b = a; a = depth[x.f]; } } else { if (depth[x.f] + x.s >= a) { b = a; a = depth[x.f] + x.s; } else if (depth[x.f] + x.s >= b)b = depth[x.f] + x.s; } } } maxdia = max(maxdia, a + b); } up.rsz(n, -1); F0R(i, n) { if (up[i] == -1)up_(i, -1); } vi size(cur, inf); F0R(i, n) { multiset<int>t; trav(x, adj[i]) { if (x.f != parents[i]) { t.insert(x.s + depth[x.f]); } } t.insert(up[i]); if (sz(t) == 1)continue; size[type[i]] = min(size[type[i]], *t.rbegin()); } trav(x, size)if (x == inf)x = 0; sort(all(size), greater<int>()); return max({ maxdia,sz(size) > 1 ? size[0] + size[1] + l : 0, sz(size) > 2 ? size[1] + size[2] + 2 * l : 0 }); }
#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...