oj.uz

답안 #200078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200078 2020-02-05T09:31:36 Z godwind 꿈 (IOI13_dreaming) C++14
0 / 100
 1000 ms 8012 KB 
#include "dreaming.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], pref[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) {
		vector<int> dist(n, INF);
		dist[i] = 0;
		vector<int> q;
		q.push_back(i);
		for (int it = 0; it < (int)q.size(); ++it) {
			int v = q[it];
			for (pair<int, int> go : g[v]) {
				if (dist[v] + go.second < dist[go.first]) {
					dist[go.first] = dist[v] + go.second;
					q.push_back(go.first);
				}
			}
		}
		for (int j = 0; j < n; ++j) {
			if (dist[j] != INF) {
				uax(f[i], dist[j]);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (!used[i]) {
			order.clear();
			dfs1(i);
			int value = f[order[0]];
			for (int v : order) {
				uin(value, f[v]);
			}
			comp.push_back(value);
		}
	}
	// 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]);
	}
	pre();
	if (m == n - 1) {
		return comp[0];
	}
	int res = L + comp[0] + comp[1];
	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

*/

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 8012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 8012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 8012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1098 ms 5496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 8012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1093 ms 8012 KB Time limit exceeded
2 Halted 0 ms 0 KB -