Submission #707282

#	Time	Username	Problem	Language	Result	Execution time	Memory
707282		mseebacher	Race (IOI11_race)	C++17	9 / 100	554 ms	111132 KiB

race

//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const lld pi = 3.14159265358979323846;

#define MAXI (int)2e5+5
 
vector<int> ad[MAXI];
vector<vector<int>> dp(MAXI,vector<int>(105,1e9));

 
map<pair<int,int>,int> paths;
int len = 0;
 
void dfs(int x,int e){
	for(auto s: ad[x]){
		if(s == e) continue;
		dfs(s,x);
		for(int i  = paths[{s,x}];i<=len;i++){
			dp[x][i] = min(dp[x][i],dp[s][i-paths[{s,x}]]+1);
		}
		
	}
	
}
 
int best_path(int n, int k, int h[][2], int l[]){
	len = k;
	for(int i = 0;i<n-1;i++){
		int u = h[i][0];
		int v = h[i][1];
		ad[u].push_back(v);
		ad[v].push_back(u);
		paths.insert({{u,v},l[i]});
		paths.insert({{v,u},l[i]});
	}
	for(int i = 0;i<n;i++){
		dp[i][0] = 0;
	}
	dfs(0,0);
	int ans = 1e9;
	for(int i = 0;i<n;i++){
		ans = min(ans,dp[i][k]);
	}
	if(ans == 1e9) ans = -1;
	return ans;
}

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