| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 262228 |
2020-08-12T13:50:06 Z |
evpipis |
Islands (IOI08_islands) |
C++11 |
|
1280 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
const int len = 1e6+5;
int deg[len], n, ccs;
ii par[len];
ll dep[len], best[len];
ll val[2*len], pref[2*len];
vector<int> order[len];
vector<ii> adj[len];
void dfs1(int u, int col){
while (deg[u] == 2){
deg[u] = 1;
order[col].pb(u);
u = par[u].fi;
}
}
void find_spec(){
queue<int> myq;
for (int i = 1; i <= n; i++){
deg[i] = adj[i].size();
if (deg[i] == 1)
myq.push(i);
}
while (!myq.empty()){
int u = myq.front(), p = par[u].fi;
myq.pop();
deg[p]--, deg[u]--;
if (deg[p] == 1)
myq.push(p);
}
ccs = 0;
for (int i = 1; i <= n; i++)
if (deg[i] == 2)
dfs1(i, ccs++);
/*printf("ccs = %d\n", ccs);
for (int i = 0; i < ccs; i++){
printf("cc#%d:", i);
for (auto u: order[i])
printf(" %d", u);
printf("\n");
}*/
}
ll dfs2(int st){
vector<int> vec;
stack<int> mys;
mys.push(st);
while (!mys.empty()){
int u = mys.top();
mys.pop();
vec.pb(u);
for (auto v: adj[u])
if (v.fi != par[u].fi && !deg[v.fi])
mys.push(v.fi);
}
ll ans = 0;
reverse(vec.begin(), vec.end());
for (auto u: vec){
ll mx1 = 0, mx2 = 0;
for (auto v: adj[u]){
if (v.fi == par[u].fi || deg[v.fi])
continue;
dep[u] = max(dep[u], dep[v.fi]+v.se);
if (dep[v.fi]+v.se > mx1)
swap(mx1, mx2), mx1 = dep[v.fi]+v.se;
else if (dep[v.fi]+v.se > mx2)
mx2 = dep[v.fi]+v.se;
}
ans = max(ans, mx1+mx2);
}
return ans;
}
void find_diam(){
for (int i = 0; i < ccs; i++)
for (auto u: order[i])
best[i] = max(best[i], dfs2(u));
//for (int i = 0; i < ccs; i++)
// printf("best_without_specs[%d] = %lld\n", i, best[i]);
}
ll path(vector<int> &vec){
ll ans = 0;
int m = vec.size();
for (int i = 0; i < 2*m; i++)
val[i] = dep[vec[i%m]];
for (int i = 0; i < 2*m-1; i++)
pref[i+1] = pref[i]+par[vec[i%m]].se;
deque<int> deq;
for (int i = 0; i < 2*m; i++){
while (!deq.empty() && i-deq.front()+1 > m)
deq.pop_front();
if (!deq.empty())
ans = max(ans, pref[i]+val[i] + val[deq.front()]-pref[deq.front()]);
while (!deq.empty() && val[i]-pref[i] >= val[deq.back()]-pref[deq.back()])
deq.pop_back();
deq.push_back(i);
}
return ans;
}
void find_path(){
for (int i = 0; i < ccs; i++)
best[i] = max(best[i], path(order[i]));
//for (int i = 0; i < ccs; i++)
// printf("best_final[%d] = %lld\n", i, best[i]);
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++){
int p, c;
scanf("%d %d", &p, &c);
adj[i].pb(mp(p, c));
adj[p].pb(mp(i, c));
par[i] = mp(p, c);
}
find_spec();
find_diam();
find_path();
ll ans = 0;
for (int i = 0; i < ccs; i++)
ans += best[i];
printf("%lld\n", ans);
return 0;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
140 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
islands.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
143 | scanf("%d %d", &p, &c);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47352 KB |
Output is correct |
| 2 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 3 |
Correct |
28 ms |
47360 KB |
Output is correct |
| 4 |
Correct |
28 ms |
47360 KB |
Output is correct |
| 5 |
Correct |
32 ms |
47232 KB |
Output is correct |
| 6 |
Correct |
28 ms |
47360 KB |
Output is correct |
| 7 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 8 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 9 |
Correct |
29 ms |
47360 KB |
Output is correct |
| 10 |
Correct |
28 ms |
47360 KB |
Output is correct |
| 11 |
Correct |
29 ms |
47352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
47360 KB |
Output is correct |
| 2 |
Correct |
29 ms |
47360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47480 KB |
Output is correct |
| 2 |
Correct |
42 ms |
47608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
48256 KB |
Output is correct |
| 2 |
Correct |
68 ms |
49940 KB |
Output is correct |
| 3 |
Correct |
47 ms |
48632 KB |
Output is correct |
| 4 |
Correct |
38 ms |
47992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
51064 KB |
Output is correct |
| 2 |
Correct |
90 ms |
53680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
59588 KB |
Output is correct |
| 2 |
Correct |
167 ms |
61400 KB |
Output is correct |
| 3 |
Correct |
192 ms |
67568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
261 ms |
70264 KB |
Output is correct |
| 2 |
Correct |
316 ms |
83192 KB |
Output is correct |
| 3 |
Correct |
424 ms |
85284 KB |
Output is correct |
| 4 |
Correct |
438 ms |
98924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
454 ms |
110420 KB |
Output is correct |
| 2 |
Correct |
1024 ms |
119776 KB |
Output is correct |
| 3 |
Correct |
471 ms |
94148 KB |
Output is correct |
| 4 |
Correct |
623 ms |
116028 KB |
Output is correct |
| 5 |
Correct |
642 ms |
117408 KB |
Output is correct |
| 6 |
Correct |
1128 ms |
105456 KB |
Output is correct |
| 7 |
Correct |
742 ms |
127912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
571 ms |
102272 KB |
Output is correct |
| 2 |
Correct |
497 ms |
102300 KB |
Output is correct |
| 3 |
Correct |
783 ms |
131072 KB |
Output is correct |
| 4 |
Correct |
763 ms |
125152 KB |
Output is correct |
| 5 |
Correct |
594 ms |
131072 KB |
Output is correct |
| 6 |
Correct |
521 ms |
118432 KB |
Output is correct |
| 7 |
Correct |
1280 ms |
119432 KB |
Output is correct |
