Submission #1258331

#TimeUsernameProblemLanguageResultExecution timeMemory
1258331Szymon_PilipczukDreaming (IOI13_dreaming)C++20
18 / 100
34 ms13888 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define st first #define nd second #define pb push_back #define all(a) a.begin(),a.end() #define rep(a,b) for(int a = 0;a<b;a++) const int inf = 1e9; const ll infl = 1e18; int d[100000]; int mxd[100000]; bool vis[100000]; vector<vector<pair<int,int>>> gr; void cd(int v) { //cerr<<v<<"\n"; vis[v] = true; for(pair<int,int> i : gr[v]) { if(!vis[i.st]) { cd(i.st); mxd[v] = max(mxd[v], i.nd + mxd[i.st]); } } } int mx; void dfs(int v,int md) { vis[v] = true; vector<pair<int,int>> vv; for(pair<int,int> i : gr[v]) { if(!vis[i.st]) { vv.pb({mxd[i.st] + i.nd,i.st}); } } sort(all(vv)); reverse(all(vv)); vv.pb({0,-1}); mx = min(mx,max(md,vv[0].st)); for(int i = 1;i<vv.size()-1;i++) { dfs(vv[i].nd,max(md,vv[0].st) + vv[i].st - mxd[vv[i].nd]); } if(vv[0].nd != -1) dfs(vv[0].nd,max(md,vv[1].st) + vv[0].st - mxd[vv[0].nd]); } int travelTime(int n,int m,int l,int a[],int b[],int t[]) { gr.resize(n); rep(i,m) { gr[a[i]].pb({b[i],t[i]}); gr[b[i]].pb({a[i],t[i]}); } rep(i,n) { if(!vis[i]) { cd(i); } } vector<int> aa; rep(i,n) vis[i] = false; rep(i,n) { if(!vis[i]) { mx = inf; dfs(i,0); aa.pb(mx); } } sort(all(aa)); reverse(all(aa)); //rep(i,aa.size()) cerr<<aa[i]<<"\n"; if(aa.size() == 1) { return aa[0]; } else if(aa.size() == 2) { return aa[0] + aa[1] + l; } else { return max(aa[0] + aa[1] + l, aa[1] + aa[2] + l * 2); } }
#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...