Submission #1077060

#TimeUsernameProblemLanguageResultExecution timeMemory
1077060MrPavlitoDreaming (IOI13_dreaming)C++17
0 / 100
33 ms13908 KiB
#include "dreaming.h" #include <bits/stdc++.h> //#define int long long #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define sc second #define pii pair<int,int> using namespace std; const int MAXN = 1e5+5; const int mod7 = 1e9+7; const long long inf = 1e18; int n; bool visited[MAXN]; int parents[MAXN]; vector<vector<pii>> graf(MAXN); vector<long long> dist; long long mxdist; long long rez = inf; void dfs1(int nod, int p, long long d, int &kraj) { parents[nod] = p; visited[nod] = 1; if(d>=mxdist) { kraj = nod; mxdist = d; } for(auto x: graf[nod])if(x.fi!=p)dfs1(x.fi, nod, d+x.sc, kraj); } void dfs2(int nod, int p, long long d) { rez = min(rez, max(mxdist -d, d)); int tr = rez; for(auto x: graf[nod]) { if(x.fi == p)continue; int p1 = parents[x.fi]; if(parents[x.fi] == nod && parents[x.fi] != x.fi) { dfs2(x.fi, nod, d+x.sc); } } } void solve(int i) { int nod1; mxdist = 0; dfs1(i,i,0, nod1); int nod2; mxdist = 0; dfs1(nod1, nod1, 0, nod2); rez = inf; dfs2(nod1, nod1, 0); int tr = rez; dist.pb(rez); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n = N; for(int i=0; i<M; i++) { graf[A[i]].pb(mp(B[i], T[i])); graf[B[i]].pb(mp(A[i], T[i])); } for(int i=0; i<n; i++)if(!visited[i])solve(i); sort(all(dist)); reverse(all(dist)); //for(auto x: dist)cout << x<< " ";cout << endl; long long konacno = dist[0]; if(M == n-1)return konacno; konacno = max(konacno,dist[0]+dist[1]+L); for(int i=2; i<dist.size(); i++) konacno = max(konacno,dist[0]+dist[i]+2*L); return konacno; }

Compilation message (stderr)

dreaming.cpp: In function 'void dfs2(int, int, long long int)':
dreaming.cpp:44:13: warning: unused variable 'p1' [-Wunused-variable]
   44 |         int p1 = parents[x.fi];
      |             ^~
dreaming.cpp:40:9: warning: unused variable 'tr' [-Wunused-variable]
   40 |     int tr = rez;
      |         ^~
dreaming.cpp: In function 'void solve(int)':
dreaming.cpp:63:9: warning: unused variable 'tr' [-Wunused-variable]
   63 |     int tr = rez;
      |         ^~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=2; i<dist.size(); i++) konacno = max(konacno,dist[0]+dist[i]+2*L);
      |                  ~^~~~~~~~~~~~
#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...