Submission #1196696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196696		cowwycow	Race (IOI11_race)	C++20	100 / 100	344 ms	98228 KiB

race

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdb = pair<db, db>;
using ppii = pair<int, pii>;
using ull = unsigned long long;
using vvi = vector<vector<ll>>;

void file(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 1e9;

int n; ll k;
vector<pii> e[N];
int ans = inf;

map<ll, int> mp[N];

void dfs(int u, int par, int dep, ll dist){
	ll cur = k + dist * 2;
	mp[u][dist] = dep;
	for(auto edge : e[u]){
		int v = edge.first; ll w = edge.second;
		if(v == par) continue;
		dfs(v, u, dep + 1, dist + w);
		if(mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
		for(auto i : mp[v]){
			if(mp[u].find(cur - i.first) != mp[u].end()){
				ans = min(ans, i.second + mp[u][cur - i.first] - dep * 2);
			}
		}
		for(auto i : mp[v]){
			if(mp[u].find(i.first) == mp[u].end()){
				mp[u][i.first] = i.second;
			}else{
				mp[u][i.first] = min(mp[u][i.first], i.second);
			}
		}
	}
}

int best_path(int N, int K, int edges[][2], int weights[]){
	n = N;
	k = K;
	for(int i = 0; i < n - 1; i++){
		int u = edges[i][0], v = edges[i][1], w = weights[i];
		u++; v++;
		e[u].push_back({v, w});
		e[v].push_back({u, w});
	}
	dfs(1, -1, 0, 0);
	if(ans == inf) ans = -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void file()':
race.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(name".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:18:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |                 freopen(name".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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