| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 639113 |
2022-09-08T15:34:57 Z |
puppy |
Islands (IOI08_islands) |
C++17 |
|
691 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<int, int>> adj[1000005];
bitset<1000005> visited;
bitset<1000005> cycle;
pair<int, int> parent[1000005];
int cyc, cyc2;
int cycval;
long long dp[1000005];
vector<int> vc;
void dfs(const int &v, const int &p, const int &asg)
{
visited[v] = true;
parent[v] = make_pair(p, asg);
int cnt = 0;
int tmp;
for(auto &i:adj[v]){
if(i.first==p){
++cnt;
if(cnt==1) tmp = i.second;
else{
if(cyc == -1){
cyc = v;
cyc2 = i.first;
cycle[v] = true;
cycval = (tmp == asg) ? i.second : tmp;
}
}
continue;
}
if(visited[i.first]){
if(cyc == -1){
cyc = v;
cyc2 = i.first;
cycval = i.second;
cycle[v] = true;
}
continue;
}
dfs(i.first, v, i.second);
}
}
int par;
void treedfs(int v, int prv)
{
vc.push_back(v);
for(auto &i:adj[v]){
if(i.first == prv || cycle[i.first]) continue;
dp[i.first] = dp[v] + i.second;
treedfs(i.first, v);
}
}
void treedfs2(int v, int prv)
{
for(auto &i:adj[v]){
if(cycle[i.first] && i.first != par) continue;
if(i.first == prv) continue;
dp[i.first] = dp[v] + i.second;
treedfs2(i.first, v);
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
long long ans = 0;
cin>>N;
int tmp, k;
for(int i=1;i<=N;i++){
cin>>tmp>>k;
adj[tmp].push_back(make_pair(i, k));
adj[i].push_back(make_pair(tmp, k));
}
for(int i=0;i<1000005;i++) adj[i].shrink_to_fit();
int cycstart, cycend, tt;
long long cur, dsp, sub;
long long backup;
long long m; int loc;
vector<int> fun, val;
for(int i=1;i<=N;i++){
if(visited[i]) continue;
long long tmpans = 0;
vector<int>().swap(fun);
vector<int>().swap(val);
cyc = -1;
cyc2 = -1;
dfs(i, 0, 0);
cycstart = cyc;
cycend = cyc2;
fun.push_back(cycstart);
val.push_back(cycval);
while(cycstart != cycend){
tt = parent[cycstart].second;
cycstart = parent[cycstart].first;
cycle[cycstart] = true;
fun.push_back(cycstart);
val.push_back(tt);
}
fun.shrink_to_fit();
val.shrink_to_fit();
for(int i:fun){
par = i;
vector<int>().swap(vc);
treedfs(i, i);
vc.shrink_to_fit();
m = -1;
for(int k:vc){
if(dp[k] > m){
m = dp[k];
loc = k;
}
}
backup = m;
dp[loc] = 0;
treedfs2(loc, loc);
m = -1;
for(int k:vc) m = max(m, dp[k]);
tmpans = max(tmpans, m);
dp[i] = backup;
}
multiset<long long> heap;
cur = dsp = sub = 0;
for(int i=1;i<(int)fun.size();i++){
cur += val[i];
heap.insert(cur+dp[fun[i]]);
}
tmpans = max(tmpans, *--heap.end()+dp[fun[0]]);
for(int i=1;i<(int)fun.size();i++){
dsp += val[i];
heap.erase(heap.find(dsp + dp[fun[i]]));
sub += val[i];
cur += val[i-1];
heap.insert(cur+dp[fun[i-1]]);
tmpans = max(tmpans, *--heap.end()+dp[fun[i]]-sub);
}
heap.clear();
cur = dsp = sub = 0;
for(int i=(int)fun.size()-2;i>=0;i--){
cur += val[i+1];
heap.insert(cur+dp[fun[i]]);
}
tmpans = max(tmpans, *--heap.end()+dp[fun.back()]);
for(int i=(int)fun.size()-2;i>=0;i--){
sub += val[i+1];
dsp += val[i+1];
cur += val[(i+2)%val.size()];
heap.erase(heap.find(dsp+dp[fun[i]]));
heap.insert(cur+dp[fun[(i+1)%fun.size()]]);
tmpans = max(tmpans, *--heap.end() + dp[fun[i]]-sub);
}
ans += tmpans;
}
cout<<ans<<'\n';
}
Compilation message
islands.cpp: In function 'void dfs(const int&, const int&, const int&)':
islands.cpp:28:28: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
28 | cycval = (tmp == asg) ? i.second : tmp;
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:116:21: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
116 | treedfs2(loc, loc);
| ~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23764 KB |
Output is correct |
| 3 |
Correct |
14 ms |
23892 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 5 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 6 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 7 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 9 |
Correct |
14 ms |
23772 KB |
Output is correct |
| 10 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 11 |
Correct |
15 ms |
23764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23892 KB |
Output is correct |
| 2 |
Correct |
15 ms |
23860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
23956 KB |
Output is correct |
| 2 |
Correct |
18 ms |
24276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
24788 KB |
Output is correct |
| 2 |
Correct |
40 ms |
27604 KB |
Output is correct |
| 3 |
Correct |
26 ms |
25160 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
29008 KB |
Output is correct |
| 2 |
Correct |
78 ms |
30844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
105 ms |
36708 KB |
Output is correct |
| 2 |
Correct |
199 ms |
44788 KB |
Output is correct |
| 3 |
Correct |
243 ms |
56868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
46092 KB |
Output is correct |
| 2 |
Correct |
333 ms |
76900 KB |
Output is correct |
| 3 |
Correct |
671 ms |
86852 KB |
Output is correct |
| 4 |
Correct |
687 ms |
118588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
282 ms |
86628 KB |
Output is correct |
| 2 |
Runtime error |
691 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
309 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
