Submission #719253

#	Time	Username	Problem	Language	Result	Execution time	Memory
719253		KingJt	Race (IOI11_race)	C++17	9 / 100	114 ms	8324 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define bn binary_search
#define sz(x) int((x).size())
#define lz(x) long long((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 1000000007
#define pfx(x) partial_sum(all(x),(x).begin())
#define sfx(x) partial_sum(rall(x),(x).rbegin())
#define minl(x) min_element(all(x))
#define maxl(x) max_element(all(x))
#define itn(x,y) iota(all(x),y)
#define accu(x,y) accumulate(all(x),y)
#define yes cout<<"Y"<<"E"<<"S"<<endl
#define no cout<<"N"<<"O"<<endl
#define mx INT_MAX
#define mn INT_MIN
#define lin(x) for(int i=0;i<sz(x);i++) cin>>x[i]
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ll> vl;
typedef pair<ll,ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<pair<int,ii>> gw;
typedef vector<pair<ll,il>> lw;
typedef vector<vc> vvc;
vector<vii> lmao;
vb vis;
int dfs(int u,int pes,int len, int k){
	for(auto v : lmao[u]){
		if(vis[v.F]){
			if(pes==k) return len;
			return mx;
		}
		vis[v.F]=true;
		pes+=v.S;
		len++;
		//cout<<pes<<endl;
		if(pes==k){
			return len;
		}
		if(pes<k){
			return dfs(v.F,pes,len,k);
		}
		if(pes>k){
			return mx;
		}
	}
	if(pes==k) return len;
	return mx;
}
int best_path(int n,int k, int h[][2], int l[]){
	lmao.assign(n,vii());
	vis.assign(n,false);
	for(int i=0;i<n-1;i++){
		lmao[h[i][0]].pb({h[i][1],l[i]});
		lmao[h[i][1]].pb({h[i][0],l[i]});
	}
	int ans=mx;
	for(int i=0;i<n;i++){
		ans=min(ans,dfs(i,0,0,k));
		//cout<<ans<<endl;
		vis.assign(n,false);
	}
	//ans=min(ans,dfs(0,0,0,k));
	if(ans==mx) return -1;
	return ans;
}/*
int main(){
	int n,k;
	cin>>n>>k;
	int h[n-1][2];
	for(int i=0;i<n-1;i++){
		cin>>h[i][0]>>h[i][1];
	}
	int l[n-1];
	for(int i=0;i<n-1;i++) cin>>l[i];
	cout<<best_path(n,k,h,l)<<endl;
}*/

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