# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
676702 |
2022-12-31T18:09:07 Z |
QwertyPi |
Islands (IOI08_islands) |
C++14 |
|
615 ms |
131072 KB |
#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 |
Correct |
14 ms |
23764 KB |
Output is correct |
2 |
Correct |
12 ms |
23764 KB |
Output is correct |
3 |
Correct |
13 ms |
23892 KB |
Output is correct |
4 |
Correct |
13 ms |
23764 KB |
Output is correct |
5 |
Correct |
12 ms |
23764 KB |
Output is correct |
6 |
Correct |
12 ms |
23764 KB |
Output is correct |
7 |
Correct |
12 ms |
23792 KB |
Output is correct |
8 |
Correct |
11 ms |
23764 KB |
Output is correct |
9 |
Correct |
12 ms |
23764 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
14 ms |
23852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23892 KB |
Output is correct |
2 |
Correct |
12 ms |
23892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23996 KB |
Output is correct |
2 |
Correct |
17 ms |
24276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
24992 KB |
Output is correct |
2 |
Correct |
27 ms |
27836 KB |
Output is correct |
3 |
Correct |
20 ms |
25172 KB |
Output is correct |
4 |
Correct |
16 ms |
24420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
29428 KB |
Output is correct |
2 |
Correct |
43 ms |
32104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
38148 KB |
Output is correct |
2 |
Correct |
85 ms |
46960 KB |
Output is correct |
3 |
Correct |
111 ms |
56440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
48596 KB |
Output is correct |
2 |
Correct |
215 ms |
75756 KB |
Output is correct |
3 |
Correct |
204 ms |
88848 KB |
Output is correct |
4 |
Correct |
246 ms |
107948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
273 ms |
83484 KB |
Output is correct |
2 |
Runtime error |
615 ms |
131072 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
307 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |