Submission #830273

#	Time	Username	Problem	Language	Result	Execution time	Memory
830273		fanwen	Race (IOI11_race)	C++17	0 / 100	2 ms	4948 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

const int MAXN = 2e5 + 5;
const int MAXK = 1e6 + 5;
const int INF = 1e9;

int n, k, avail[MAXN], sz[MAXN], exist[MAXK], cntE[MAXK];
vector <pair <int, int>> adj[MAXN];
long long ans;

int dfs_size(int u, int par) {
	sz[u] = 1;
	for (auto [v, _] : adj[u]) if(v != par and !avail[v]) {
		sz[u] += dfs_size(v, u);
	}
	return sz[u];
}

int dfs_centroid(int u, int par, int n) {
	for (auto [v, _] : adj[u]) if(v != par and !avail[v]) {
		if(sz[v] > n / 2) return dfs_centroid(v, u, n);
	}
	return u;
}

int times;

int DFS(int u, int par, int cnt, int depth, int t, vector<pair<int, int>> &tmp) {
	int ans = INF;
	if(depth > k) return INF;
	int wants = k - depth;
	if(exist[wants] == t) minimize(ans, cnt + cntE[wants]);
	tmp.emplace_back(depth, cnt);
	for (auto [v, w] : adj[u]) if(v != par and !avail[v]) {
		ans = min(ans, DFS(v, u, cnt + 1, depth + w, t, tmp));
	}
	return ans;
}

int solve(int u, int par) {
	int n = dfs_size(u, par);	
	avail[u = dfs_centroid(u, par, n)] = true;
	int ans = INF;
	int t = ++times;
	exist[0] = t, cntE[0] = 0;
	for (auto [v, w] : adj[u]) if(v != par and !avail[v]) {
		vector <pair <int, int>> tmp;
		ans = min(ans, DFS(v, u, 1, w, t, tmp));
		for (auto [d, c] : tmp) {
			if(exist[d] != t || (exist[d] == t and cntE[d] > c)) {				
				exist[d] = t;
				cntE[d] = c;
			}
			cout << d << " " << c << '\n';
		}
		cout << v << '\n';
	}
	for (auto [v, _] : adj[u]) if(v != par and !avail[v]) {
		ans = min(ans, solve(v, u));
	}
	return ans;
}

int best_path(int a, int b, int H[][2], int L[]) {
	n = a, k = b;
	REP(i, n - 1) {
		adj[H[i][0] + 1].emplace_back(H[i][1] + 1, L[i]);
		adj[H[i][1] + 1].emplace_back(H[i][0] + 1, L[i]);
	}
	ans = solve(1, 0);
	return (ans >= INF ? -1 : ans);
}

#ifdef LOCAL

#include "race.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 500000

int N, K;
int H[MAX_N][2];
int L[MAX_N];
int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
	freopen("TASK.inp", "r", stdin);
	freopen("TASK.out", "w", stdout);
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}

#endif

// Dream it. Wish it. Do it.

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