Submission #376095

#	Time	Username	Problem	Language	Result	Execution time	Memory
376095		SavicS	Dreaming (IOI13_dreaming)	C++14	47 / 100	117 ms	17108 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 pref[maxn];
int br = 0;
int d[maxn];
pii last[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;
				}
				last[u] = {v, w}; 
				q.push(u);
			}
		}
	}
	int x = b;
	vector<pii> put;
	while(x != a){
		pii z = last[x];
		put.pb(z);
		x = z.fi;
	}
	put.pb({b, 0});
	ff(i,0,sz(put) - 1){
		if(i == 0)pref[i] = put[i].se;
		else pref[i] = pref[i - 1] + put[i].se;
	}
//	for(auto c : put)cout << c.fi << " " << c.se << endl;
//	ff(i,0,sz(put) - 1)cout << pref[i] << " ";
//	cout << endl;
	int rez = inf;
	int ko = 0;
	ff(i,0,sz(put) - 1){
		int mx = max(pref[i], pref[sz(put) - 1] - pref[i]);
		if(mx < rez){
			rez = mx;
			ko = put[i].fi;
		}
	}
	if(ko == 0)ko = s;
	return {ko, dia};
}

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);
		}
	}
	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

**/

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23