oj.uz

답안 #488899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
488899 2021-11-20T18:58:49 Z ssense 꿈 (IOI13_dreaming) C++14
0 / 100
 20 ms 2536 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define nax 200005
#define pb push_back
#define sc second
#define fr first
//#define int unsigned long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
 
const int N = 105;
 
vector<pair<int, int>> adj[N];
 
int bfs(int s)
{
	queue<pair<pair<int, int>, int>> q;
	q.push({{s, -1}, 0});
	int now = 0;
	while(!q.empty())
	{
		int node = q.front().fr.fr;
		int dist = q.front().sc;
		int parent = q.front().fr.sc;
		now = max(now, dist);
		q.pop();
		for(auto v : adj[node])
		{
			if(v.fr != parent)
			{
				q.push({{v.fr, node}, dist+v.sc});
			}
		}
	}
	return now;
}
 
bool vis[N];
 
int dfs(int u, int par)
{
	int ans = bfs(u);
	vis[u] = true;
	for(auto v : adj[u])
	{
		if(v.fr != par)
		{
			ans = min(ans, dfs(v.fr, u));
		}
	}
	return ans;
}
 
int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
	assert(m <= 3);
	assert(m == n-2);
	for(int i = 0; i < n; i++)
	{
		adj[i].clear();
		vis[i] = false;
	}
	for(int i = 0; i < m; i++)
	{
		adj[a[i]].pb({b[i], t[i]});
		adj[b[i]].pb({a[i], t[i]});
	}
	int ans = 0;
	vint mx;
	for(int i = 0; i < n; i++)
	{
		mx.pb(dfs(i, -1));
	}
	sort(all(mx));
	ans+=mx[mx.size()-1];
	ans+=mx[mx.size()-2];
	ans+=l;
	return ans;
}
/*
int main()
{
	int n, m, l;
	cin >> n >> m >> l;
	int a[m], b[m], t[m];
	for(int i = 0; i < m; i++)
	{
		cin >> a[i] >> b[i] >> t[i];
	}
	cout << travelTime(n, m, l, a, b, t) << endl;
}
 */
/*
 7
 5
 2
 0 1 10
 0 5 5
 5 4 6
 3 2 2
 2 6 1
 
 8 6 3
 0 1 1
 1 2 1
 1 3 1
 1 4 10
 4 5 10
 6 7 7
 
 2 0 2
 
 3 1 10
 1 2 1
 */

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 2536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 2536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 1100 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 20 ms 2536 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -