| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1111133 |
2024-11-11T15:08:42 Z |
FubuGold |
Race (IOI11_race) |
C++14 |
|
5 ms |
22096 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const int INF = 1e9 + 5;
vector<pair<int,int>> adj[MAXN+1];
int n;
long long k;
int ans = INF;
struct Node {
int offset_len = 0;
long long offset_weight = 0;
map<long long,int> mp;
int get_len(long long x) {
x -= offset_weight;
auto it = mp.find(x);
if (it == mp.end()) return INF;
return it->second + offset_len;
}
void merge_node(Node &nd) {
for (auto it = nd.mp.begin(); it != nd.mp.end(); it++) {
long long x = it->first + nd.offset_weight;
int l = it->second + nd.offset_len;
if (x <= k) {
int tmp = get_len(k - x);
if (tmp != INF) ans = min(ans,tmp + offset_len + l);
}
x -= offset_weight;
l -= offset_len;
auto tmp_it = mp.find(x);
if (tmp_it == mp.end()) mp[x] = l;
else tmp_it->second = min(tmp_it->second,l);
}
}
};
Node nd[MAXN+1];
int sz[MAXN+1];
int cal_sz(int u,int p) {
sz[u] = 1;
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i].first;
if (v == p) continue;
sz[u] += cal_sz(v,u);
}
return sz[u];
}
void dfs(int u,int p) {
int mx_v = -1;
int mx_v_w = 0;
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i].first;
if (v == p) continue;
dfs(v,u);
if (mx_v == -1 || sz[mx_v] < v) {
mx_v = v;
mx_v_w = adj[u][i].second;
}
}
nd[u].mp[0] = 0;
if (mx_v != -1) {
swap(nd[mx_v],nd[u]);
nd[u].offset_len++;
nd[u].offset_weight += mx_v_w;
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i].first;
if (v == p || v == mx_v) continue;
nd[v].offset_len++;
nd[v].offset_weight += adj[u][i].second;
nd[u].merge_node(nd[v]);
}
}
ans = min(ans,nd[u].get_len(k));
// cout << '\n';
// cout << u << ' ' << mx_v << ' ' << nd[u].offset_len << ' ' << nd[u].offset_weight << '\n';
// for (auto debug_x : nd[u].mp) {
// cout << debug_x.first << ' ' << debug_x.second << '\n';
// }
}
int best_path(int _n,int _k,int h[][2],int l[]) {
n = _n;
k = _k;
for (int i=0;i<n-1;i++) {
int x = h[i][0], y = h[i][1];
int w = l[i];
x++,y++;
adj[x].push_back(make_pair(y,w));
adj[y].push_back(make_pair(x,w));
}
if (k == 0) return 0;
cal_sz(1,-1);
dfs(1,-1);
if (ans == INF) return -1;
return ans;
}
//int _h[MAXN+1][2],_l[MAXN+1];
//int main() {
// cin.tie(0) -> sync_with_stdio(0);
// int t,c; cin >> t >> c;
// for (int i=0;i<t-1;i++) {
// cin >> _h[i][0] >> _h[i][1];
// }
// for (int i=0;i<t-1;i++) cin >> _l[i];
// cout << best_path(t,c,_h,_l);
// return 0;
//}
Compilation message
race.cpp: In function 'int cal_sz(int, int)':
race.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int)':
race.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
race.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i=0;i<adj[u].size();i++) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
22096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
