oj.uz

Submission #887016

# Submission time Handle Problem Language Result Execution time Memory
887016 2023-12-13T12:55:59 Z BBart888 Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 16980 KB 
#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
#include "dreaming.h"


using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;



const int MAXN = 2e5 + 11; 
using ll = long long;
typedef vector<int> lnum;
const int base = 1e9;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;



/*
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if ((name.size())) {
		freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
*/


int n, m, l;
vector<pair<int,ll>> adj[MAXN];
vector<int> cmp;
bool vis[MAXN];
ll dp[MAXN];

void dfs1(int v, int p)
{
	vis[v] = true;
	dp[v] = 0;
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		dfs1(u.first, v);
		dp[v] = max(dp[v], dp[u.first] + u.second);
	}
}

int center;
ll dist;
void dfs2(int v, ll mx, int p)
{
	ll mx1 = 0;
	ll  mx2 = 0;
	int id = 0;

	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		ll x = dp[u.first] + u.second;
		if (x > mx1)
		{
			mx2 = mx1;
			mx1 = x;
			id = u.first;
		}
		else if (x > mx2)
			mx2 = x;
	}

	ll mxx = max(mx1,mx);
	if (mxx < dist)
	{
		dist = mxx;
		center = v;
	}

	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		if (u.first == id)
			swap(mx1, mx2);
		dfs2(u.first, max(mx1, mx) + u.second, v);
		if (u.first == id)
			swap(mx1, mx2);
	}
}


ll diam;
int diamv;

void dfs3(int v, ll L, int p)
{
	if (L > diam)
	{
		diam = L;
		diamv = v;
	}
	for (auto u : adj[v])
	{
		if (u.first != p)
			dfs3(u.first, L + u.second, v);
	}

}

vector<int> comp;
int travelTime(int N, int M, int L, int a[], int b[], int t[])
{
	n = N;
	m = M;
	l = L;

	for (int i = 0; i < n; i++)
	{
		adj[a[i] + 1].push_back({ b[i] + 1 ,t[i]});
		adj[b[i] + 1].push_back({ a[i] + 1 ,t[i]});
	}
	ll mx = 0;
	int vert = 0;
	for (int i = 1; i <= n; i++)
	{
		if (vis[i])
			continue;
		dist = 1e9;
		center = i;
		dfs1(i, i);
		dfs2(i,0,i );

		comp.push_back(center);
		if (dist > mx)
		{
			mx = dist;
			vert = comp.back();
		}

	}

	for (auto v : comp)
	{
		if (v != vert)
		{
			adj[v].push_back({ vert,l });
			adj[vert].push_back({ v,l });
		}
	}

	dfs3(1, 0, 1);
	dfs3(diamv, 0, diamv);



	return diam;
}




/*


int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	//setIO("time");
	
	


	






	return 0;
}



*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 16980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 16980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 14544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 7768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 16980 KB Output isn't correct
2 Halted 0 ms 0 KB -