제출 #1197299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197299		nub	Race (IOI11_race)	C++20	21 / 100	469 ms	327680 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ci const int
#define cll const long long
#define cull const unsigned long long
#define fi first
#define se second
#define psb push_back
#define ppb pop_back
#define ps push
#define pp pop
using namespace std;

string file_name = "";
string input_extension = "";
string output_extension = "";

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
	return uniform_int_distribution<ll>(l, r)(rng);
}

ci inf = 1e9;
ci neginf = -1e9;
cll inf_ll = 1e18;
cll neginf_ll = -1e18;

cll MOD = 1e18;

ll mulmod(ll a, ll b){
	return (a%MOD)*(b%MOD)%MOD;
}

ll binpow(ll a, ll b){
	if (b == 0) return 1;
	if (b == 1) return a%MOD;
	if (b%2 == 0) return binpow(mulmod(a, a), b/2);
	else return mulmod(a, binpow(mulmod(a, a), b/2));
}

ll invmod(ll a){
	return binpow(a, MOD-2);
}

ci N = 2e5+1;
vector<vector<pair<int, int>>> adj;
map<int, int> mp[N];
int n, k, res = inf;

void dfs(int cur, int par){
	mp[cur][0] = 0;
	int p, w;
	int len, dis;
	for (pair<int, int> temp : adj[cur]){
		p = temp.fi; w = temp.se;
		if (p == par) continue;
		dfs(p, cur);
		
		for (pair<int, int> i : mp[p]){
			len = i.fi + w;
			dis = i.se + 1;
			if (len > 1e6) continue;
			if (mp[cur].count(k-len) > 0){
				res = min(res, dis + mp[cur][k-len]);
			}
		}
		for (pair<int, int> i : mp[p]){
			len = i.fi + w;
			dis = i.se + 1;
			if (mp[cur].count(len) == 0) mp[cur][len] = dis;
			else mp[cur][len] = min(mp[cur][len], dis);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	adj.resize(n);
	int s, e, w;
	for (int i=0; i<n-1; i++){
		s = H[i][0];
		e = H[i][1];
		w = L[i];
		adj[s].psb({e, w});
		adj[e].psb({s, w});
	}
	dfs(0, -1);
	if (res == inf) return -1;
	else return res;
}

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