oj.uz

답안 #887013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887013 2023-12-13T12:39:26 Z BBart888 꿈 (IOI13_dreaming) C++14
0 / 100
 37 ms 20436 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);
	}
}
*/



ll dp[MAXN];
vector<pair<int,int>> adj[MAXN];
bool vis[MAXN];
vector<int> cmp;
int node;
vector<pair<ll, int>> vv;
int par[MAXN];
ll lon[MAXN];

void dfs1(int v, int p)
{
	vis[v] = true;
	cmp.push_back(v);

	if (dp[v] > dp[node])
		node = v;

	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		par[u.first] = v;
		dp[u.first] = dp[v] + u.second;
		dfs1(u.first, v);
	}
}


void calc(int v, int p)
{
	
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		calc(u.first, v);
		lon[v] = max(lon[v], lon[u.first] + u.second);
	}

}


int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
	for (int i = 0; i < m; i++)
	{
		adj[a[i] + 1].push_back({ b[i] + 1 ,t[i]});
		adj[b[i] + 1].push_back({ a[i] + 1 ,t[i]});
	}

	for (int i = 1; i <= n; i++)
	{
		if (vis[i] == 0)
		{
			node = 0;
			dfs1(i, -1);
			for (int v : cmp)
				dp[v] = 0,par[v] =0;
			cmp.clear();
			dfs1(node, -1);
			int curr = node;
			vector<int> path;
			while (curr != 0)
			{
				path.push_back(curr);
				curr = par[curr];
			}
			if (path.size() == 0)
				path.push_back(i);
			
			int sz = path.size();
			int V = path[path.size() / 2];
			calc(V, -1);
			ll val1 = lon[V];
			for (auto v : cmp)
				lon[v] = 0;
			V = path[(path.size() - 1) / 2];
			calc(V, -1);
			ll tmp = lon[V];
			if (val1 < lon[V])
				V = path[path.size() / 2];
			val1 = min(val1, tmp);

			vv.push_back({ val1,V });
			cmp.clear();
		}
	}


	sort(vv.rbegin(), vv.rend());


	ll fin = vv[0].first;


	for (int i = 1; i < vv.size(); i++)
	{
		fin = max(fin,vv[0].first + vv[i].first + l);
	}



	return fin;
}


/*


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


	






	return 0;
}



*/

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:121:8: warning: unused variable 'sz' [-Wunused-variable]
  121 |    int sz = path.size();
      |        ^~
dreaming.cpp:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |  for (int i = 1; i < vv.size(); i++)
      |                  ~~^~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 20436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 20436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 13056 KB Output is correct
2 Incorrect 20 ms 13008 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 20436 KB Output isn't correct
2 Halted 0 ms 0 KB -