Submission #376104

#	Time	Username	Problem	Language	Result	Execution time	Memory
376104		SavicS	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KiB

dreaming

//#include"dreaming.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, m, L;

vector<pii> g[maxn];

int br = 0;
int d[maxn];
int par[maxn];
int used[maxn];
int was[maxn];
pii bfs(int s){
	queue<int> q;
	q.push(s);
	used[s] = br;
	int a = 0;
	int mx = 0;
	while(!q.empty()){
		int v = q.front(); q.pop();
		for(auto c : g[v]){
			int u = c.fi;
			int w = c.se;
			if(!used[u]){
				used[u] = br;
				d[u] = d[v] + w;
				if(d[u] > mx){
					mx = d[u];
					a = u;
				}
				q.push(u);
			}
		}
	}
	was[a] = br;
	d[a] = 0;
	q.push(a);
	int dia = 0;
	int b = 0;
	while(!q.empty()){
		int v = q.front(); q.pop();
		for(auto c : g[v]){
			int u = c.fi;
			int w = c.se;
			if(!was[u]){
				was[u] = br;
				d[u] = d[v] + w;
				if(d[u] > dia){
					dia = d[u];
					b = u;
				}
				par[u] = v;
				q.push(u);
			}
		}
	}
	int x = b;
	int ans = dia;
	int ko = 0;
	while(x != 0){
		int kol = max(d[x], dia - d[x]);
		if(ans > kol){
			ans = kol;
			ko = x;
		}
		x = par[x];
	}
	return {ko, ans};
}

int dia = 0;
int dfs(int v, int p, int duz){
	int best = duz;	
	for(auto c : g[v]){
		int u = c.fi;
		int w = c.se;
		if(u != p){
			int dist = dfs(u, v, duz + w);
			dia = max(dia, best + dist - 2 * duz);
			best = max(best, dist);
		}
	}
	return best;
}

bool cmp(pii s1, pii s2){
	return s1.se > s2.se;
}

int travelTime(int N, int M, int L1, int A[], int B[], int T[]){
	n = N;
	m = M;
	L = L1;
	ff(i,0,m - 1){
		int u = A[i] + 1;
		int v = B[i] + 1;
		int w = T[i];
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	vector<pii> vec;
	ff(i,1,n){
		if(!used[i]){
			br += 1;
			pii x = bfs(i);
			vec.pb(x);
		}
	}
	sort(all(vec), cmp);
	ff(i,1,sz(vec) - 1){
		g[vec[0].fi].pb({vec[i].fi, L});
		g[vec[i].fi].pb({vec[0].fi, L});
	}
	dfs(1, -1, 0);
	return dia;
}


int main()
{
   	ios::sync_with_stdio(false);
   	cout.tie(nullptr);
  	cin.tie(nullptr);
	cin >> n >> m >> L;
	ff(i,1,m){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	vector<pii> vec;
	ff(i,1,n){
		if(!used[i]){
			br += 1;
			pii x = bfs(i);
			vec.pb(x);
		}
	}
	sort(all(vec), cmp);
	ff(i,1,sz(vec) - 1){
		g[vec[0].fi].pb({vec[i].fi, L});
		g[vec[i].fi].pb({vec[0].fi, L});
	}
	dfs(1, -1, 0);
	cout << dia << endl;
   	return 0;
}
/**

4 3 2
1 2 6
2 3 10
3 4 3


12 8 2
1 9 4
9 3 2
3 8 4
12 6 3
6 2 7
10 2 5
2 4 1
7 11 3

// probati bojenje sahovski ili slicno

**/

Compilation message (stderr)

/tmp/cc33Titb.o: In function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccsDXSBu.o:grader.c:(.text.startup+0x0): first defined here
/tmp/ccsDXSBu.o: In function `main':
grader.c:(.text.startup+0xc9): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status