#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 11;
// 16
vector<vector<pair<int, int>>> G(N);
// 32
int p[N], w[N], tin[N], t = 0;
long long dp[N];
bool vis[N], cyc[N];
// 12
struct edge{
int u, v, w;
};
vector<edge> extra;
void dfs(int id, int v, int pa = -1){
vis[v] = true; tin[v] = ++t;
for(auto i : G[v]){
if(!vis[i.fi]){
p[i.fi] = v;
dfs(id, i.fi, v);
w[i.fi] = i.se;
}else if(i.fi != pa){
extra[id] = {v, i.fi, i.se};
}
}
}
bool is_anc(int u, int v){
return tin[u] <= tin[v];
}
long long dfs_dp(int id, int v, int pa = -1){
long long mx1 = 0, mx2 = 0;
long long ans = 0;
for(auto i : G[v]){
if(!cyc[i.fi] && i.fi != pa){
long long r = dfs_dp(id, i.fi, v);
ans = max(ans, r);
long long v = dp[i.fi] + i.se;
if(v > mx1) mx2 = mx1, mx1 = v;
else if(v > mx2) mx2 = v;
}
}
ans = max(ans, mx1 + mx2); dp[v] = mx1;
return ans;
}
long long solve(int id, vector<long long>& DP, vector<long long>& W){
int n = W.size();
for(int i = 0; i < n; i++){
W.push_back(W[i]);
}
W.push_back(0);
for(int i = (int) W.size() - 2; i >= 0; i--){
W[i] = W[i + 1] - W[i];
}
// 4
deque<int> v;
for(int i = 0; i < n; i++){
while(v.size() && DP[i] + W[i] >= DP[v.back()] + W[v.back()]) v.pop_back();
v.push_back(i);
}
long long ans = 0;
for(int i = 0; i < n; i++){
if(v.front() == i) v.pop_front();
ans = max(ans, DP[i] - W[i] + DP[v.front() % n] + W[v.front()]);
while(v.size() && DP[i] + W[i + n] >= DP[v.back() % n] + W[v.back()]) v.pop_back();
v.push_back(i + n);
}
return ans;
}
int32_t main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
int n; cin >> n;
for(int i = 1; i <= n; i++){
int v, _w; cin >> v >> _w;
G[i].push_back({v, _w});
G[v].push_back({i, _w});
}
for(int i = 1; i <= n; i++){
G[i].shrink_to_fit();
}
/*
for(int i = 1; i <= n; i++){
if(!vis[i]){
extra.resize(extra.size() + 1);
dfs(extra.size() - 1, i);
}
}
// 20
int CC = extra.size();
long long ans = 0;
for(int i = 0; i < CC; i++){
vector<int> cyc_L, cyc_R;
int x = extra[i].u, y = extra[i].v;
while(!is_anc(x, y)){
cyc[x] = true;
cyc_L.push_back(x);
x = p[x];
}
while(!is_anc(y, x)){
cyc[y] = true;
cyc_R.push_back(y);
y = p[y];
}
int l = x;
cyc[l] = true;
long long rans = 0;
for(auto v : cyc_L){
rans = max(rans, dfs_dp(i, v));
}
for(auto v : cyc_R){
rans = max(rans, dfs_dp(i, v));
}
rans = max(rans, dfs_dp(i, l));
vector<long long> W, DP;
for(auto i : cyc_L){
DP.push_back(dp[i]);
W.push_back(w[i]);
}
DP.push_back(dp[l]);
for(int i = (int) cyc_R.size() - 1; i >= 0; i--){
DP.push_back(dp[cyc_R[i]]);
W.push_back(w[cyc_R[i]]);
}
cyc_L.resize(0); cyc_R.resize(0);
W.push_back(extra[i].w);
rans = max(rans, solve(i, DP, W));
ans += rans;
}
cout << ans << endl;
*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
23764 KB |
Output isn't correct |
| 2 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 3 |
Incorrect |
12 ms |
23768 KB |
Output isn't correct |
| 4 |
Incorrect |
15 ms |
23892 KB |
Output isn't correct |
| 5 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 6 |
Incorrect |
12 ms |
23812 KB |
Output isn't correct |
| 7 |
Incorrect |
12 ms |
23788 KB |
Output isn't correct |
| 8 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 9 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 10 |
Incorrect |
13 ms |
23780 KB |
Output isn't correct |
| 11 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
24400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
25680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
31304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
114 ms |
38360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
275 ms |
70712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
262 ms |
70420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
