oj.uz

Submission #719253

# Submission time Handle Problem Language Result Execution time Memory
719253 2023-04-05T16:59:46 Z KingJt Race (IOI11_race) C++17
9 / 100
 114 ms 8324 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 228 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 228 KB Output is correct
19 Incorrect 1 ms 212 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 228 KB Output is correct
19 Incorrect 114 ms 8324 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 308 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 228 KB Output is correct
19 Incorrect 1 ms 212 KB Output isn't correct
20 Halted 0 ms 0 KB -