Submission #815067

#TimeUsernameProblemLanguageResultExecution timeMemory
815067AcanikolicDreaming (IOI13_dreaming)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "dreaming.h" #define pb push_back //#define int long long #define F first #define S second using namespace std; const int N = 1e5+10; const int mod = 1e9+7; const int inf = 1e18; vector<pair<int,int>>g[N]; vector<int>all,dist(N),vis(N); void dfs(int x,int par) { all.pb(x); for(auto X:g[x]) { if(X.F != par) { dist[X.F] = dist[x] + X.S; dfs(X.F,x); } } } pair<int,int>nadji_precnik(int root) { int x,y; all.clear(); dist[root] = 0; dfs(root,0); int mx = 0,idx = -1; for(auto X:all) { if(dist[X] >= mx) { mx = dist[X]; idx = X; } } x = idx; mx = 0,idx = -1; all.clear(); dist[x] = 0; dfs(x,0); for(auto X:all) { //cout << "X = " << X << " dist[x] = " << dist[X] << endl; if(dist[X] >= mx) { mx = dist[X]; idx = X; } } //cout << endl; //cout << idx << endl; y = idx; //if(root == 4) cout << "x = " << x << " y = " << y << endl; return {x,y}; } void obelezi(int x) { if(vis[x]) return; vis[x] = 1; for(auto X:g[x]) obelezi(X.F); } int travelTime(int N,int M,int L,vector<int>A,vector<int>B,vector<int>T) { for(int i=0;i<M;i++) { g[A[i]].pb({B[i],T[i]}); g[B[i]].pb({A[i],T[i]}); } vector<int>centers; for(int i=0;i<N;i++) { if(vis[i]) continue; //cout << i << endl; all.clear(); dfs(i,0); vector<int>all_in_comp = all; pair<int,int>dia = nadji_precnik(i); int X = dia.F,Y = dia.S; //if(i == 4) cout << X << ' ' << Y << endl; dist[X] = 0; dfs(X,0); map<int,int>D; for(auto XX:all_in_comp) D[XX] = dist[XX]; dist[Y] = 0; dfs(Y,0); for(auto XX:all_in_comp) D[XX] = max(D[XX],dist[XX]); int mn = 1e9,idx = -1; for(auto XX:all_in_comp) { if(D[XX] < mn) { mn = D[XX]; idx = XX; } } //cout << "root = " << i << " dia = " << X << " " << Y << endl; //cout << "root = " << i << " center = " << idx << endl; centers.pb(idx); obelezi(i); } for(int i=1;i<centers.size();i++) { g[centers[i-1]].pb({centers[i],L}); g[centers[i]].pb({centers[i-1],L}); } pair<int,int> res = nadji_precnik(1); dist[res.F] = 0; dfs(res.F,0); int index = 0; for(int i=0;i<N;i++) { if(dist[index] <= dist[i]) index = i; } return dist[index]; } /*signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,m,l; cin >> n >> m >> l; vector<int>a(m),b(m),c(m); for(int i=0;i<m;i++) cin >> a[i]; for(int i=0;i<m;i++) cin >> b[i]; for(int i=0;i<m;i++) cin >> c[i]; cout << travelTime(n,m,l,a,b,c); return 0; }*/

Compilation message (stderr)

dreaming.cpp:19:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int inf = 1e18;
      |                 ^~~~
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |  for(int i=1;i<centers.size();i++) {
      |              ~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccc5IbwI.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status