| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 715323 |
2023-03-26T13:00:49 Z |
Ahmed57 |
Islands (IOI08_islands) |
C++14 |
|
814 ms |
131072 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
using namespace std;
deque<pair<long long, long long>> qq;
long long getMax(){
return qq.front().first;
}
void add(pair<long long,long long> p){
while (!qq.empty() && qq.back().first <= p.first)qq.pop_back();
qq.push_back(p);
}
void rem(pair<long long,long long> p){
if (!qq.empty() && qq.front() == p) qq.pop_front();
}
stack<int> st;
vector<vector<int>> all;
vector<pair<int,pair<int,int>>> adj[1000001];
bool tmp[1000001];
bool vis[1000001];
bool ss = 0;
void cycle(int i,int pr){
st.push(i);
if(tmp[i]){
vector<int> cyc;
cyc.push_back(i);
st.pop();
while(st.top()!=i){
cyc.push_back(st.top());st.pop();
}
for(int j = cyc.size()-1;j>=0;j--)st.push(cyc[j]);
all.push_back(cyc);
st.pop();
ss = 1;
return;
}
tmp[i] = 1;
for(auto j:adj[i]){
if(j.second.second==pr)continue;
cycle(j.first,j.second.second);
if(ss){
tmp[i] = 0;
st.pop();
return ;
}
}
tmp[i] = 0;
st.pop();
}
void fil(int i){
vis[i]=1;
for(auto j:adj[i]){
if(!vis[j.first]){
fil(j.first);
}
}
}
long long maxDep[1000005];
long long TreeDim[1000005];
bool ele[1000005];
long long cost[1000001];
int sst,node;long long maa;
void ma(int i,int pr,long long dep){
maxDep[sst] =max(maxDep[sst],dep);
for(auto j:adj[i]){
if(j.first==pr||ele[j.first]==1)continue;
ma(j.first,i,dep+j.second.first);
}
}
void Dim(int i,int pr,long long dep){
if(maa<dep){
maa =dep;
node = i;
}
TreeDim[sst] =max(TreeDim[sst],dep);
for(auto j:adj[i]){
if(j.first==pr||ele[j.first]==1)continue;
Dim(j.first,i,dep+j.second.first);
}
}
signed main(){
int n;cin>>n;
map<pair<int,int>,int>mp;
for(int i = 1;i<=n;i++){
int a,b;
cin>>a>>b;
mp[{i,a}] = b;
mp[{a,i}] = b;
adj[i].push_back({a,{b,i}});
adj[a].push_back({i,{b,i}});
}
for(int i = 1;i<=n;i++){
if(!vis[i]){
ss = 0;
cycle(i,-1);
fil(i);
}
}
long long sum = 0;
for(auto i:all){
int len = i.size();
for(int j = 0;j<i.size();j++){
ele[i[(j+1)%len]] = 1;
ele[i[((j-1)%len+len)%len]] = 1;
sst = i[j];maa = -1,node = i[j];
ma(i[j],-1,0);
Dim(node,-1,0);
maa = -1;
Dim(node,-1,0);
ele[i[(j+1)%len]] = 0;
ele[i[((j-1)%len+len)%len]] = 0;
}
if(i.size()==2){
long long ans = max(TreeDim[i[0]],TreeDim[i[1]]);
int e = 0;
for(auto j:adj[i[0]]){
if(j.first==i[1])e = max(e,j.second.first);
}
ans = max(ans,maxDep[i[0]]+maxDep[i[1]]+e);
sum+=ans;
continue;
}
long long ans = 0;
for(auto j:i)ans = max(ans,TreeDim[j]);
//cout<<ans<<endl;
multiset<pair<long long,int>> s;
long long sz = mp[{i[0],i[1]}];
vector<pair<long long,long long>> pai;
for(int j = 1;j<i.size();j++){
//cout<<i[j]<<"hh"<<(-sz)+maxDep[i[j]]<<endl;
pai.push_back({(-sz)+maxDep[i[j]],i[j]});
cost[i[j]] = (-sz)+maxDep[i[j]];
//cout<<sz<<"\n";
sz+=mp[{i[j],i[(j+1)%len]}];
}
reverse(pai.begin(),pai.end());
for(auto j:pai){
add(j);
}
ans = max(ans,maxDep[i[0]]+sz+getMax());
//cout<<(*it).second<<"\n";
//cout<<ans<<endl;
//cout<<i[0]<<" "<<i[1]<<"\n";
long long global = 0;
for(int j = i.size()-1;j>=1;j--){
pair<long long,long long> p = {(-global)+maxDep[i[(j+1)%len]],i[(j+1)%len]};
add(p);
cost[i[(j+1)%len]] = (-global)+maxDep[i[(j+1)%len]];
global-=mp[{i[j],i[(j+1)%len]}];
p={cost[i[j]],i[j]};
rem(p);
ans = max(ans,(maxDep[i[j]]+sz+getMax())+global);
//cout<<(maxDep[i[j]]+sz+(*it).first)+global<<endl;
}
sum+=ans;
while(!qq.empty())qq.pop_back();
}
cout<<sum<<endl;
}
Compilation message
islands.cpp: In function 'int main()':
islands.cpp:102:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int j = 0;j<i.size();j++){
| ~^~~~~~~~~
islands.cpp:129:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int j = 1;j<i.size();j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
13 ms |
23892 KB |
Output is correct |
| 3 |
Correct |
14 ms |
23908 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 |
23780 KB |
Output is correct |
| 7 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 9 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 10 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 11 |
Correct |
14 ms |
23764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
15 ms |
24020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
24148 KB |
Output is correct |
| 2 |
Correct |
19 ms |
24788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
26960 KB |
Output is correct |
| 2 |
Correct |
78 ms |
32688 KB |
Output is correct |
| 3 |
Correct |
52 ms |
27896 KB |
Output is correct |
| 4 |
Correct |
29 ms |
25776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
36308 KB |
Output is correct |
| 2 |
Correct |
149 ms |
45260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
303 ms |
64948 KB |
Output is correct |
| 2 |
Correct |
374 ms |
75464 KB |
Output is correct |
| 3 |
Correct |
421 ms |
94412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
523 ms |
102708 KB |
Output is correct |
| 2 |
Runtime error |
487 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
814 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
806 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
