Submission #379343

#	Time	Username	Problem	Language	Result	Execution time	Memory
379343		pavement	Dreaming (IOI13_dreaming)	C++17	100 / 100	210 ms	17760 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int ty, st, md, dist[100005][2];
bool vis[100005];
vector<int> vec;
vector<ii> adj[100005];

void dfs(int n, int e = -1, int d = 0) {
	if (ty != -1) dist[n][ty] = d;
	else vec.pb(n);
	if (d > md) {
		md = d;
		st = n;
	}
	for (auto u : adj[n])
		if (u.first != e)
			dfs(u.first, n, d + 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]].eb(B[i], T[i]);
		adj[B[i]].eb(A[i], T[i]);
	}
	vector<ii> proc;
	for (int i = 0; i < N; i++) {
		if (!vis[i]) {
			vec.clear();
			md = -1;
			ty = -1;
			dfs(i);
			md = -1;
			ty = 0;
			dfs(st);
			ty = 1;
			dfs(st);
			int curm = INT_MAX, cent = -1;
			for (int j : vec) {
				if (max(dist[j][0], dist[j][1]) < curm) {
					curm = max(dist[j][0], dist[j][1]);
					cent = j;
				}
				vis[j] = 1;
			}
			proc.eb(curm, cent);
		}
	}
	sort(proc.begin(), proc.end(), greater<ii>());
	for (int i = 1; i < proc.size(); i++) {
		adj[proc[0].second].eb(proc[i].second, L);
		adj[proc[i].second].eb(proc[0].second, L);
	}
	md = ty = -1;
	dfs(0);
	dfs(st);
	return md;
}

Compilation message (stderr)

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

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23