Submission #495727

#	Time	Username	Problem	Language	Result	Execution time	Memory
495727		luanaamorim	Race (IOI11_race)	C++14	0 / 100	0 ms	332 KiB

race

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring>
#include <set>
#include <stack>
#include <bitset>
#include <race.h>
#define ll long long
#define INF (1e9)
#define MAX (int) (1e3 + 5)
#define MOD 1000000007
#define par pair<int, int>
#define all(v) v.begin(), v.end()
#define sz(x) (int) ((x).size())
#define esq(x) (x<<1)
#define dir(x) ((x<<1)|1)
#define lsb(x) (x & -x)
#define W(x) cout << #x << ": " << x << endl
#define Wii(x) cout << x.first << ' ' << x.second << endl
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n, k, a, b, c, sub[MAX], vis[MAX], maior;
vector<par> grafo[MAX];
par f[MAX];

int dfs(int u, int p = 0)
{
	if (vis[u]) return 0;
	sub[u] = 1;
	for (auto[v, w] : grafo[u])
		if (v!=p) sub[u] += dfs(v, u);
	return sub[u];
}

int centroid(int u, int p, int t)
{	
	for (auto[v, w] : grafo[u])
		if (v!=p && !vis[v] && sub[v]>t/2) return centroid(v, u, t);
	return u; 
}

int query(int u, int p, int h, int d)
{	
	if (vis[u] || d>k) return INF;
	maior = max(maior, h);
	int resp = INF;
	if (f[k-d].first) resp = f[k-d].second + h;

	for (auto[v, w] : grafo[u])
		if (v!=p) resp = min(resp, query(v, u, h+1, d+w));
	return resp;
}

void update(int u, int p, int h, int d)
{
	if (vis[u] || d>k) return;
	if (f[d].first) f[d].second = min(f[d].second, h);
	else f[d].second = h;
	f[d].first=1;

	for (auto[v, w] : grafo[u])
		if (v!=p) update(v, u, h+1, d+w);
}

int solve(int u)
{
	dfs(u);
	int c = centroid(u, 0, sub[u]);
	vis[c] = 1;
	int resp = INF;
	for (int i = 0; i < MAX; i++)
		f[i] = {0, 0};

	maior = 0;
	for (auto[v, w] : grafo[c])
	{
		resp = min(resp, query(v, 0, 1, w));
 		update(v, 0, 1, w);
	}	

	for (auto[v, w] : grafo[c])
		if (!vis[v]) resp = min(resp, solve(v));

	return resp;
}

int best_path(int n, int k, int h[][2], int l[])
{_
	for (int i = 1; i < n; i++)
	{
		grafo[h[i][0]+1].push_back({h[i][1]+1, l[i]});
		grafo[h[i][1]+1].push_back({h[i][0]+1, l[i]});
	}

	int resp = solve(1);
	return (resp==INF ? -1 : resp);
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int)':
race.cpp:38:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |  for (auto[v, w] : grafo[u])
      |           ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:45:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |  for (auto[v, w] : grafo[u])
      |           ^
race.cpp: In function 'int query(int, int, int, int)':
race.cpp:57:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |  for (auto[v, w] : grafo[u])
      |           ^
race.cpp: In function 'void update(int, int, int, int)':
race.cpp:69:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |  for (auto[v, w] : grafo[u])
      |           ^
race.cpp: In function 'int solve(int)':
race.cpp:83:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |  for (auto[v, w] : grafo[c])
      |           ^
race.cpp:89:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   89 |  for (auto[v, w] : grafo[c])
      |           ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57