Submission #340116

#TimeUsernameProblemLanguageResultExecution timeMemory
340116iliccmarkoDreaming (IOI13_dreaming)C++14
100 / 100
110 ms21868 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" #define INF 1000000000 #define LINF 1000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];} #define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;} #define single_case solve(); #define line cout<<"------------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); } int maksd; const int N = 1e5 + 5; int vidjen[N]; vector<vector<pair<int, int > > > g(N); vector<int> v; int mm, s; vector<vector<pair<int, int> > > path(N); void najdalji(int u, int pret, int d) { vidjen[u] = 1; if(d>=mm) { mm = d; s = u; } for(auto x : g[u]) { if(x.first==pret) continue; najdalji(x.first, u, x.second+d); } } bool get_path(int u, int pret, int k, int parent, int d) { vidjen[u] = 1; if(u==k) { path[parent].pb({u, d}); return true; } for(auto x : g[u]) { if(x.first==pret) continue; if(get_path(x.first, u, k, parent, x.second)) { path[parent].pb({u, d}); return true; } } return false; } int travelTime(int n, int m, int l, int a[], int b[], int t[]) { for(int i = 0;i<m;i++) { int x = a[i]; int y = b[i]; int l = t[i]; g[x].pb({y, l}); g[y].pb({x, l}); } for(int i = 0;i<n;i++) { if(vidjen[i]) continue; mm = 0; s = i; int l1; najdalji(i, -1, 0); l1 = s; mm = 0; s = l1; int l2; najdalji(l1, -1, 0); l2 = s; get_path(l1, -1, l2, i, 0); int sum = 0; int c; int mini = INF; int m2 = 0; int p = 0; for(auto x : path[i]) sum += x.second; for(auto x : path[i]) { p += x.second; if(abs(p - (sum - p)) < mini) { m2 = max(p, abs(sum - p)); mini = abs(p - abs((sum - p))); c = x.first; } } maksd = max(maksd, sum); v.pb(m2); } sort(all(v), greater<int>()); int ans = maksd; if(len(v)==1) { return ans; } ans = max(ans, v[0]+v[1]+l); if(len(v)>=3) { ans = max(ans, v[1] + v[2] + 2*l); } return ans; }

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:86:13: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   86 |         int c;
      |             ^
#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...