| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 763990 |
2023-06-23T04:43:03 Z |
nonono |
Hard route (IZhO17_road) |
C++14 |
|
8 ms |
11988 KB |
#include "bits/stdc++.h"
#define int long long
using namespace std;
void file(string name = ""){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(name != ""){
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
void _max(pair<int, int> &a, pair<int, int> b){
if(a.first < b.first){
a = b;
} else
if(a.first == b.first){
a.second += b.second;
}
}
const int mxN = 5e5 + 10;
int n;
vector<vector<int>> adj(mxN);
pair<int, int> d[mxN], f[mxN], pref[mxN], suff[mxN];
int max_hardness = 0, count_path = 1;
void dfs(int u, int p){
d[u] = {0, 1};
for(int v : adj[u]){
if(v == p) continue ;
dfs(v, u);
_max(d[u], make_pair(d[v].first + 1, d[v].second));
}
}
void _dfs(int u, int p){
vector<int> b;
vector<pair<int, int>> a;
if(adj[u].size() == 1 || u > 1){
a.push_back({f[u].first + 1, f[u].second});
}
for(int v : adj[u]){
if(v == p) continue ;
a.push_back({d[v].first + 1, d[v].second});
}
sort(a.begin(), a.end(), greater<pair<int, int>> ());
if(a.size() >= 3 && a[0].first * (a[1].first + a[2].first) >= max_hardness){
int curr_hardness = a[0].first * (a[1].first + a[2].first);
int curr_path = 0;
int cnt = 0;
for(auto [x, y] : a){
if(x == a[2].first){
cnt += y;
}
}
if(a[1].first == a[2].first){
curr_path = cnt * cnt;
for(auto [x, y] : a){
if(x == a[2].first){
curr_path -= y * y;
}
}
curr_path /= 2;
} else
if(a[0].first == a[1].first){
curr_path = (a[0].second + a[1].second) * cnt;
} else {
curr_path = a[1].second * cnt;
}
if(curr_hardness > max_hardness){
max_hardness = curr_hardness;
count_path = curr_path;
} else {
count_path += curr_path;
}
}
a.clear();
for(int v : adj[u]){
if(v == p) continue ;
a.push_back({d[v].first + 1, d[v].second});
b.push_back(v);
}
pref[0] = {0, 0};
for(int i = 1; i <= a.size(); i ++){
pref[i] = pref[i - 1];
_max(pref[i], a[i - 1]);
}
suff[a.size() + 1] = {0, 0};
for(int i = a.size(); i >= 1; i --){
suff[i] = suff[i + 1];
_max(suff[i], a[i - 1]);
}
for(int i = 1; i <= a.size(); i ++){
int v = b[i - 1];
_max(f[v], pref[i - 1]);
_max(f[v], suff[i + 1]);
if(adj[u].size() == 1 || u > 1) _max(f[v], f[u]);
}
for(int i = 1; i <= a.size(); i ++){
int v = b[i - 1];
_dfs(v, u);
}
}
signed main(){
file("");
cin >> n;
for(int i = 1; i <= n - 1; i ++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 1);
f[1] = {0, 1};
_dfs(1, 1);
cout << max_hardness << " " << count_path << "\n";
return 0;
}
Compilation message
road.cpp: In function 'void _dfs(long long int, long long int)':
road.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | for(auto [x, y] : a){
| ^
road.cpp:69:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
69 | for(auto [x, y] : a){
| ^
road.cpp:99:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 1; i <= a.size(); i ++){
| ~~^~~~~~~~~~~
road.cpp:110:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i = 1; i <= a.size(); i ++){
| ~~^~~~~~~~~~~
road.cpp:117:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i = 1; i <= a.size(); i ++){
| ~~^~~~~~~~~~~
road.cpp: In function 'void file(std::string)':
road.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
9 | freopen((name + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 7 |
Incorrect |
8 ms |
11988 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 7 |
Incorrect |
8 ms |
11988 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 3 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 4 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
8 ms |
11988 KB |
Output is correct |
| 6 |
Correct |
6 ms |
11988 KB |
Output is correct |
| 7 |
Incorrect |
8 ms |
11988 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
