| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 639084 |
2022-09-08T14:21:38 Z |
puppy |
Islands (IOI08_islands) |
C++17 |
|
477 ms |
131072 KB |
#include <bits/stdc++.h>
using namespace std;
int N;
vector<pair<pair<int, int>, int>> adj[1000005];
bool visitededge[1000005];
bool visited[1000005];
bool cycle[1000005];
pair<int, int> parent[1000005];
int cyc, cyc2;
int cycval;
long long far[1000005];
long long dp[1000005];
vector<int> chd[1000005];
struct maxheap
{
priority_queue<long long> pq;
priority_queue<long long> del;
void push(long long v)
{
pq.push(v);
while(!del.empty() && del.top() == pq.top()) {
pq.pop();
del.pop();
}
}
void dsp(long long v)
{
del.push(v);
while(!del.empty() && del.top() == pq.top()) {
pq.pop();
del.pop();
}
}
long long top()
{
return pq.top();
}
void pop()
{
pq.pop();
while(!del.empty() && del.top() == pq.top()) {
pq.pop();
del.pop();
}
}
int Size()
{
return pq.size() - del.size();
}
bool isEmpty()
{
return Size() == 0;
}
void reset()
{
while(!pq.empty()) pq.pop();
while(!del.empty()) del.pop();
}
};
void dfs(int v, int p, int asg, int edgenum)
{
visitededge[edgenum] = true;
visited[v] = true;
parent[v] = make_pair(p, asg);
for(auto &i:adj[v]){
if(visitededge[i.second]) continue;
if(visited[i.first.first]){
if(cyc == -1){
cyc = v;
cyc2 = i.first.first;
cycval = i.first.second;
cycle[v] = true;
}
continue;
}
dfs(i.first.first, v, i.first.second, i.second);
}
}
void treedfs(int v, int prv, int p)
{
chd[p].push_back(v);
for(auto &i:adj[v]){
if(i.first.first == prv || cycle[i.first.first]) continue;
dp[i.first.first] = dp[v] + i.first.second;
treedfs(i.first.first, v, p);
}
}
void treedfs2(int v, int prv, int p)
{
for(auto &i:adj[v]){
if(cycle[i.first.first] && i.first.first != p) continue;
if(i.first.first == prv) continue;
dp[i.first.first] = dp[v] + i.first.second;
treedfs2(i.first.first, v, p);
}
}
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(make_pair(i, k), i));
adj[i].push_back(make_pair(make_pair(tmp, k), i));
}
for(int i=1;i<=N;i++){
if(visited[i]) continue;
long long tmpans = 0;
vector<int> fun;
vector<int> val;
cyc = -1;
cyc2 = -1;
dfs(i, 0, 0, 0);
int cycstart = cyc;
int cycend = cyc2;
int tt;
fun.push_back(cycstart);
val.push_back(cycval);
while(cycstart != cycend){
//if(cnt--) cout<<cycstart<<' '<<cycend<<'\n';
tt = parent[cycstart].second;
cycstart = parent[cycstart].first;
cycle[cycstart] = true;
fun.push_back(cycstart);
val.push_back(tt);
}
for(int i:fun){
treedfs(i, i, i);
long long m = -1, loc;
for(int k:chd[i]){
if(dp[k] > m){
m = dp[k];
loc = k;
}
}
far[i] = m;
dp[loc] = 0;
treedfs2(loc, loc, i);
m = -1;
for(int k:chd[i]) m = max(m, dp[k]);
tmpans = max(tmpans, m);
}
maxheap heap;
long long cur = 0;
long long dsp = 0;
long long sub = 0;
for(int i=1;i<(int)fun.size();i++){
cur += val[i];
heap.push(cur+far[fun[i]]);
}
tmpans = max(tmpans, heap.top()+far[fun[0]]);
for(int i=1;i<(int)fun.size();i++){
dsp += val[i];
heap.dsp(dsp + far[fun[i]]);
sub += val[i];
//모든 점에서 sub 빼야 함
cur += val[i-1];
heap.push(cur+far[fun[i-1]]);
tmpans = max(tmpans, heap.top()+far[fun[i]]-sub);
}
heap.reset();
cur = sub = 0;
for(int i=(int)fun.size()-2;i>=0;i--){
cur += val[i+1];
heap.push(cur+far[fun[i]]);
}
tmpans = max(tmpans, heap.top()+far[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.dsp(dsp+far[fun[i]]);
heap.push(cur+far[fun[(i+1)%fun.size()]]);
tmpans = max(tmpans, heap.top() + far[fun[i]]-sub);
}
ans += tmpans;
}
cout<<ans<<'\n';
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:142:21: warning: 'loc' may be used uninitialized in this function [-Wmaybe-uninitialized]
142 | treedfs2(loc, loc, i);
| ~~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47320 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
47360 KB |
Output isn't correct |
| 3 |
Correct |
26 ms |
47316 KB |
Output is correct |
| 4 |
Correct |
23 ms |
47284 KB |
Output is correct |
| 5 |
Correct |
28 ms |
47300 KB |
Output is correct |
| 6 |
Correct |
23 ms |
47376 KB |
Output is correct |
| 7 |
Correct |
24 ms |
47252 KB |
Output is correct |
| 8 |
Correct |
23 ms |
47240 KB |
Output is correct |
| 9 |
Correct |
23 ms |
47228 KB |
Output is correct |
| 10 |
Correct |
24 ms |
47256 KB |
Output is correct |
| 11 |
Correct |
24 ms |
47284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
47448 KB |
Output is correct |
| 2 |
Correct |
25 ms |
47436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47404 KB |
Output is correct |
| 2 |
Correct |
28 ms |
47816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
48964 KB |
Output is correct |
| 2 |
Correct |
56 ms |
52144 KB |
Output is correct |
| 3 |
Correct |
33 ms |
49188 KB |
Output is correct |
| 4 |
Correct |
27 ms |
48148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
54304 KB |
Output is correct |
| 2 |
Correct |
79 ms |
58456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
66872 KB |
Output is correct |
| 2 |
Correct |
162 ms |
76060 KB |
Output is correct |
| 3 |
Correct |
201 ms |
89796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
86512 KB |
Output is correct |
| 2 |
Correct |
325 ms |
115424 KB |
Output is correct |
| 3 |
Correct |
410 ms |
129940 KB |
Output is correct |
| 4 |
Runtime error |
279 ms |
131072 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
131072 KB |
Output is correct |
| 2 |
Runtime error |
477 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
317 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
