Submission #298536

# Submission time Handle Problem Language Result Execution time Memory
298536 2020-09-13T05:01:30 Z Bill_00 Dreaming (IOI13_dreaming) C++14
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
int n, m, L;
vector<pair<int, long long> > adj[100005];
bool vis[100005] = {0};
long long p = 0, res = 0;
int id = 0;
vector<long long > a;
void dfs(int u, int x, long long path)
{
	if(path >= p)
	{
		p = path;
		id = u;
	}
	vis[u] = 1;
	for(int i = 0; i < adj[u].size(); i++){
		int v = adj[u][i].first;
		long long e = adj[u][i].second;
		if(v != x) dfs(v, u, path + e);
	} 
}
int go[100005];
long long cost[100005];
void dfsd(int u, int x){
	if(cost[u] >= p)
	{
		p = cost[u];
		id = u;
	}
	go[u] = x;
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i].first;
		long long e = adj[u][i].second;
		if(v != x)
		{
			cost[v] = cost[u] + e;
			dfsd(v, u);
		}
	}
}
int travelTime(int n,int m,int L,int A[],int B[],int T[])
{
	int i, j;
	for(int i=0;i<m;i++)
	{
		adj[A[i]].pb(mp(B[i], long long(T[i])));
		adj[B[i]].pb(mp(A[i], long long(T[i])));
	}
	for(i = 0; i < n; i++)
	if(!vis[i]){
		id = 0;
		p = 0;
		dfs(i, -1, 0);
		dfsd(id, -1);
		long long W = 1e12;
		res = max(res, p);
		int u = id;
		while(u != -1)
		{
			W = min(W, max(cost[u], p - cost[u]));
			u = go[u];
		}
		a.pb(W);
	}
	sort(a.begin(), a.end());
	int sz = a.size();
	if(sz >= 2) res = max(res, a[sz - 1] + a[sz - 2] + L);
	if(sz > 2) res = max(res, a[sz - 2] + a[sz - 3] + 2 * L);
	return res; 
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int, long long int)':
dreaming.cpp:19:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i = 0; i < adj[u].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfsd(int, int)':
dreaming.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < adj[u].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:50:25: error: expected primary-expression before 'long'
   50 |   adj[A[i]].pb(mp(B[i], long long(T[i])));
      |                         ^~~~
dreaming.cpp:51:25: error: expected primary-expression before 'long'
   51 |   adj[B[i]].pb(mp(A[i], long long(T[i])));
      |                         ^~~~
dreaming.cpp:47:9: warning: unused variable 'j' [-Wunused-variable]
   47 |  int i, j;
      |         ^