Submission #122630

#	Time	Username	Problem	Language	Result	Execution time	Memory
122630		ekrem	Dreaming (IOI13_dreaming)	C++98	100 / 100	176 ms	47580 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i].st
#define yol g[node][i].nd
#define inf 1000000007
#define N 1000005
using namespace std;
typedef pair < int , int > ii;
// #define fail(s, x...) do { \
// 		fprintf(stderr, s "\n", ## x); \
// 		exit(1); \
// 	} while(0)

int dp[N], u[N], k;
ii c[N];
ii mn, mx;
vector < ii > g[N];

void hazirla(int node, int par){
	for(int i = 0; i < g[node].size(); i++){
		if(coc == par)
			continue;
		hazirla(coc, node);
		dp[node] = max(dp[node], dp[coc] + yol);
	}
}

void dfs(int node, int us){
	u[node] = 1;
	mn = min(mn, mp(max(us, dp[node]), node) );
	multiset < int > s;
	s.insert(0);
	for(int i = 0; i < g[node].size(); i++){
		if(u[coc])
			continue;
		s.insert(dp[coc] + yol);
	}

	for(int i = 0; i < g[node].size(); i++){
		if(u[coc])
			continue;
		s.erase(s.find(dp[coc] + yol));
		dfs(coc, max(us + yol, *s.rbegin() + yol));
		s.insert(dp[coc] + yol);
	}
}

void bul(int node, int par, int yoll){
	mx = max(mx, mp(yoll, node));
	for(int i = 0; i < g[node].size(); i++)
		if(coc != par)
			bul(coc, node, yoll + yol);
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
	for(int i = 0; i < m; i++){
		a[i]++;b[i]++;
		g[a[i]].pb(mp(b[i], t[i]));
		g[b[i]].pb(mp(a[i], t[i]));
	}
	// multiset < int > s;
	for(int i = 1; i <= n; i++)
		if(!u[i]){
			mn.st = inf;
			hazirla(i, 0);
			dfs(i, 0);
			c[++k] = mn;
			// cout << mn.st << " " << mn.nd << endl;
		}
	sort(c + 1, c + k + 1);
	for(int i = 1; i < k; i++){
		g[c[i].nd].pb(mp(c[k].nd, l));
		g[c[k].nd].pb(mp(c[i].nd, l));
		// cout << "AMK" << k << "AMK" << endl;
	}
	mx = mp(-inf, 0);
	bul(1, 0, 0);
	int git = mx.nd;
	mx = mp(-inf, 0);
	bul(git, 0, 0);
	return mx.st;
}



// #define MAX_N 100000

// static int A[MAX_N];
// static int B[MAX_N];
// static int T[MAX_N];

// int main() {
// 	// 	freopen("in.txt", "r", stdin);
// 	// freopen("out.txt", "w", stdout);
// 	int nnn, M, L, i;
// 	int res;

// 	res = scanf("%d%d%d", &nnn, &M, &L);
// 	for (i = 0; i < M; i++)
// 		res = scanf("%d%d%d", &A[i], &B[i], &T[i]);

// 	int answer = travelTime(nnn, M, L, A, B, T);
// 	printf("%d\n", answer);

// 	return 0;
// }

Compilation message (stderr)

dreaming.cpp:13:1: warning: multi-line comment [-Wcomment]
 // #define fail(s, x...) do { \
 ^
dreaming.cpp: In function 'void hazirla(int, int)':
dreaming.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
dreaming.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void bul(int, int, int)':
dreaming.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~

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