| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1025228 |
2024-07-16T18:04:52 Z |
mindiyak |
Race (IOI11_race) |
C++14 |
|
9 ms |
17684 KB |
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
#include "race.h"
/*
1.BFS numer of children (priority queue with visited)
2.Check children nodes with each other (set with upper and lower bound)
3.Save children distances to the parent node (save a set with distances to each leaf)
*/
vector<vpi> paths(2e5+3,vpi());
vector<map<ll,pair<ll,ll>>> dist(2e5+3,map<ll,pair<ll,ll>>());
vi children(2e5+3);
vi parent(2e5+3,-1);
vl parent_dist(2e5+3,-1);
void dfs(int pos,int prev){
int sum = 1;
for(auto node:paths[pos]){
if(node.F == prev)continue;
parent[node.F] = pos;
parent_dist[node.F] = node.S;
dfs(node.F,pos);
sum += children[node.F];
}
children[pos] = sum;
}
int best_path(int N, int K, int H[][2], int L[])
{
FOR(i,0,N-1){
paths[H[i][0]].pb({H[i][1],L[i]});
paths[H[i][1]].pb({H[i][0],L[i]});
}
dfs(0,-1);
// FOR(i,0,N)cout << children[i] << " ";
// cout << endl;
// FOR(i,0,N)cout << parent[i] << " ";
// cout << endl;
// FOR(i,0,N)cout << parent_dist[i] << " ";
// cout << endl;
priority_queue<pi> pq;
FOR(i,0,N){
pq.push({-children[i],i});
}
ll ans = 1e18;
while(!pq.empty()){
int node = pq.top().S;pq.pop();
// cout << node << " | " << endl;
for(auto a:dist[node]){
// cout << "a " << a.F << " " << K-a.F;
if(a.F > K)continue;
if(dist[node].count(K-a.F)){
// cout << " " << dist[node][K-a.F].S << " " << a.S.S << " " << a.S.F << " " << dist[node][K-a.F].F;
if(dist[node][K-a.F].S != a.S.S){
// cout << " ans - " << a.S.F+dist[node][K-a.F].F+1;
ans = min(ans,a.S.F+dist[node][K-a.F].F+1);
}
}
// cout << endl;
}
if(parent[node] == -1)continue;
// cout << "b " << parent[node] << " " << parent_dist[node] << " " << 1 << " " << node << endl;
dist[parent[node]].insert({parent_dist[node],{1,node}});
for(auto a:dist[node]){
// cout << "c " << parent[node] << " " << parent_dist[node]+a.F << " " << a.S.F+1 << " " << node << endl;
if(parent_dist[node]+a.F == K){
ans = min(ans, a.S.F+2);
}
if(parent_dist[node]+a.F >= K)continue;
dist[parent[node]].insert({parent_dist[node]+a.F,{a.S.F+1,node}});
}
// cout << endl;
}
if(ans == 1e9)return -1;
return ans-1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17684 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17576 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
17500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17684 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17576 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
17500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17684 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17576 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
17500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
17684 KB |
Output is correct |
| 2 |
Correct |
8 ms |
17576 KB |
Output is correct |
| 3 |
Incorrect |
9 ms |
17500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
