Submission #200197

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

dreaming

#include "grader.h"
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;


#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228



template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}
 
 
random_device rnd;
 
template<typename T> void shuffle(vector< T > &v) {
    for (int i = 1; i < (int)v.size(); ++i) {
        swap(v[rnd() % i], v[i]);
    }
    for (int i = (int)v.size() - 1; i; --i) {
        swap(v[rnd() % i], v[i]);
    }
}

const int N = 100 * 1000 + 228;
const int INF = 1e9 + 1000000;

int n, m, L;
int down[N], up[N], f[N];
bool used[N];
vector< pair<int, int> > g[N];

vector<int> order;

void dfs1(int v, int par = -1) {
	used[v] = 1;
	down[v] = 0;
	order.push_back(v);
	for (pair<int, int> go : g[v]) {
		int to = go.first, w = go.second;
		if (to == par) continue;
		dfs1(to, v);
		uax(down[v], down[to] + w);
	}
}

void dfs2(int v, int par = -1) {
	vector< pair<int, int> > sons;
	vector<int> value, pref, suff;
	for (pair<int, int> go : g[v]) {
		int to = go.first, w = go.second;
		if (to == par) continue;
		sons.emplace_back(to, w);
		value.push_back(w + down[to]);
	}
	int sz = (int)sons.size();
	pref.resize(sz + 2);
	suff.resize(sz + 2);
	for (int i = 0; i < sz; ++i) {
		pref[i + 1] = max(value[i], pref[i]);
	}
	for (int i = sz; i; --i) {
		suff[i] = max(suff[i + 1], value[i - 1]);
	}
	for (int i = 1; i <= sz; ++i) {
		int to = sons[i - 1].first, w = sons[i - 1].second;
		uax(up[to], up[v] + w);
		uax(up[to], w + max(pref[i - 1], suff[i + 1]));
	}
	for (int i = 0; i < sz; ++i) {
		dfs2(sons[i].first, v);
	}
}

vector<int> comp;

void pre() {
	for (int i = 0; i < n; ++i) {
		down[i] = up[i] = 0;
	}
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			order.clear();
			dfs1(i);
			dfs2(i);
			for (int v : order) {
				f[v] = max(down[v], up[v]);
			}
			int value = f[order[0]];
			for (int v : order) {
				uin(value, f[v]);
			}
			comp.push_back(value);
		}
	}
}


int travelTime(int NN, int MM, int LL, int A[], int B[], int T[])
{
	n = NN;
	m = MM;
	L = LL;
	for (int i = 0; i < m; ++i) {
		g[A[i]].emplace_back(B[i], T[i]);
		g[B[i]].emplace_back(A[i], T[i]);
	}
	// if (n <= 100) exit(-1);
	pre();
	if (m == n - 1) {
		int res = 0;
		for (int i = 0; i < n; ++i) {
			uax(res, f[i]);
		}
		return res;
	}
	if (m == n - 2) {
		int res = L + comp[0] + comp[1];
		for (int i = 0; i < n; ++i) {
			uax(res, f[i]);
		}
		return res;
	}
	sort(comp.rbegin(), comp.rend());
	int res = 0;
	uax(res, comp[0] + comp[1] + L);
	uax(res, comp[1] + comp[2] + 2 * L);
	for (int i = 0; i < n; ++i) {
		uax(res, f[i]);
	}
	return res;
}

// int A[100], B[100], T[100];

// signed main() {
// 	cin >> n >> m >> L;
// 	for (int i = 0; i < m; ++i) {
// 		cin >> A[i] >> B[i] >> T[i];
// 	}
// 	cout << travelTime(n, m, L, A, B, T) << '\n';
// }


/*

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

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

*/

Compilation message (stderr)

dreaming.cpp:1:10: fatal error: grader.h: No such file or directory
 #include "grader.h"
          ^~~~~~~~~~
compilation terminated.