| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1025436 |
2024-07-17T03:28:52 Z |
mindiyak |
Race (IOI11_race) |
C++14 |
|
131 ms |
262144 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<ll, ll> 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<vector<vpi>> dist(2e5+3,vector<vpi>(102,vpi()));
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});
}
int ans = 1e9;
while(!pq.empty()){
int node = pq.top().S;pq.pop();
// cout << node << " | " << endl;
FOR(j,0,50){
FOR(k,0,dist[node][j].size()){
pi a = dist[node][j][k];
// cout << "a " << a.F << " " << K-a.F;
FOR(i,0,dist[node][K-j].size()){
// cout << " " << itr1->S.S << " " << a.S.S << " " << a.S.F << " " << itr1->S.F;
if(dist[node][K-j][i].S != a.S){
// cout << " 1 ans - " << a.S.F+itr1->S.F+1 << endl;
ans = min(ans,a.F+dist[node][K-j][i].F+1);
}
}
// cout << endl;
}
}
if(parent[node] == -1)continue;
// cout << "b " << parent[node] << " " << parent_dist[node] << " " << 1 << " " << node << endl;
if(parent_dist[node] == K){
// cout << "2 ans - " << 2 << endl;
ans = min(ans, 2);
}
if(parent_dist[node] < K)dist[parent[node]][parent_dist[node]].pb({1,node});
FOR(j,0,100){
FOR(k,0,dist[node][j].size()){
pi a = dist[node][j][k];
// cout << "c " << parent[node] << " " << parent_dist[node]+a.F << " " << a.S.F+1 << " " << node << endl;
if(parent_dist[node]+j == K){
// cout << " 2 ans - " << a.S.F+2 << endl;
ans = min(ans, a.F+2);
}
if(parent_dist[node]+j >= K)continue;
dist[parent[node]][parent_dist[node]+j].pb({a.F+1,node});
}
}
// cout << endl;
}
if(ans == 1e9)return -1;
return ans-1;
}
Compilation message
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:21:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | #define FOR(i, a, b) for (int i = a; i < (b); i++)
| ^
race.cpp:92:7: note: in expansion of macro 'FOR'
92 | FOR(k,0,dist[node][j].size()){
| ^~~
race.cpp:21:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | #define FOR(i, a, b) for (int i = a; i < (b); i++)
| ^
race.cpp:95:9: note: in expansion of macro 'FOR'
95 | FOR(i,0,dist[node][K-j].size()){
| ^~~
race.cpp:21:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | #define FOR(i, a, b) for (int i = a; i < (b); i++)
| ^
race.cpp:115:7: note: in expansion of macro 'FOR'
115 | FOR(k,0,dist[node][j].size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
131 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
