| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1037605 |
2024-07-29T05:48:34 Z |
8pete8 |
Islands (IOI08_islands) |
C++17 |
|
464 ms |
131072 KB |
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6+5,inf=1e9,minf=-1e9,lg=25;
int n,m,k,x,y,q,z=0;
vector<pii>adj[mxn+10];
int have=0;
pii up[mxn+10];
int dp1[mxn+10],mx;
bitset<mxn+10>on,vis;
void dfs(int cur,int p){
vis[cur]=on[cur]=1;
for(auto i:adj[cur]){
if(i.f==p)continue;
if(vis[i.f]&&on[i.f]){
x=cur,y=i.f,z=i.s;
have++;
}
if(!vis[i.f])dfs(i.f,cur);
}
on[cur]=0;
}
void dfs1(int cur,int p){//dont take edge x,y
vector<int>take;
for(auto i:adj[cur]){
if(i.f==p)continue;
if(cur==x&&i.f==y)continue;
if(cur==y&&i.f==x)continue;
up[i.f]={cur,i.s};
dfs1(i.f,cur);
dp1[cur]=max(dp1[cur],dp1[i.f]+i.s);
take.pb(dp1[i.f]+i.s);
}
sort(all(take));
mx=max(mx,dp1[cur]);
if(take.size()>1)mx=max(mx,take.back()+take[take.size()-2]);
}
map<pii,int>mp;
//find diameter
int32_t main(){
fastio
cin>>n;
for(int i=1;i<=n;i++){
int a,b;cin>>a>>b;
pii x={min(a,i),max(a,i)};
if(mp.find(x)==mp.end())mp[x]=b;
else mp[x]=max(mp[x],b);
}
for(auto i:mp){
adj[i.f.f].pb({i.f.s,i.s});
adj[i.f.s].pb({i.f.f,i.s});
}
int ans=0;
for(int i=1;i<=n;i++){
if(vis[i])continue;
have=0,z=0,x=i,mx=0;
if(have>1)assert(0);//we should only have atmost 1 cycle?
dfs(i,-1);
dfs1(x,-1);
if(have){
//passing through edge x,y
vector<pii>cycle;
while(y!=x){
cycle.pb({y,up[y].s});
on[y]=1;
y=up[y].f;
}
cycle.pb({x,0});
on[x]=1;
reverse(all(cycle));
vector<int>pref(cycle.size()),suf(cycle.size());
for(int i=1;i<cycle.size();i++)pref[i]=cycle[i].s+pref[i-1];
for(int i=cycle.size()-2;i>=0;i--)suf[i]=cycle[i+1].s+suf[i+1];
for(auto i:cycle){
dp1[i.f]=0;
for(auto j:adj[i.f])if(!on[j.f])dp1[i.f]=max(dp1[i.f],dp1[j.f]+j.s);
}
for(int i=0;i<cycle.size();i++){
pref[i]=pref[i]+dp1[cycle[i].f];
if(i)pref[i]=max(pref[i],pref[i-1]);
}
for(int i=cycle.size()-1;i>=0;i--){
suf[i]=suf[i]+dp1[cycle[i].f];
if(i+1<cycle.size())suf[i]=max(suf[i],suf[i+1]);
if(i)mx=max(mx,pref[i-1]+suf[i]+z);
}
}
ans+=mx;
}
cout<<ans<<'\n';
}
/*
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
9
2 1
5 1
1 1
3 1
4 1
4 1
5 1
1 1
3 1
a node cant be in multiple cycle
** there can be atmost 1 cycle for each comp
compute each comp independtly
how to solve a tree?
nvm we are finding diameter smh
*/
Compilation message
islands.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
32 | #pragma GCC optimize ("03,unroll-lopps")
| ^
islands.cpp:42:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
42 | void dfs(int cur,int p){
| ^
islands.cpp:54:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
54 | void dfs1(int cur,int p){//dont take edge x,y
| ^
islands.cpp:71:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
71 | int32_t main(){
| ^
islands.cpp: In function 'int32_t main()':
islands.cpp:104:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=1;i<cycle.size();i++)pref[i]=cycle[i].s+pref[i-1];
| ~^~~~~~~~~~~~~
islands.cpp:110:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i=0;i<cycle.size();i++){
| ~^~~~~~~~~~~~~
islands.cpp:116:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | if(i+1<cycle.size())suf[i]=max(suf[i],suf[i+1]);
| ~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29016 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 3 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 4 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 5 |
Correct |
4 ms |
29020 KB |
Output is correct |
| 6 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 7 |
Correct |
5 ms |
28796 KB |
Output is correct |
| 8 |
Correct |
4 ms |
29020 KB |
Output is correct |
| 9 |
Correct |
7 ms |
29016 KB |
Output is correct |
| 10 |
Correct |
4 ms |
29020 KB |
Output is correct |
| 11 |
Correct |
5 ms |
29016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
29020 KB |
Output is correct |
| 2 |
Correct |
5 ms |
29136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
29016 KB |
Output is correct |
| 2 |
Correct |
7 ms |
29788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
27 ms |
38104 KB |
Output is correct |
| 3 |
Correct |
16 ms |
33624 KB |
Output is correct |
| 4 |
Correct |
10 ms |
30300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
40388 KB |
Output is correct |
| 2 |
Correct |
49 ms |
47020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
59340 KB |
Output is correct |
| 2 |
Correct |
113 ms |
75388 KB |
Output is correct |
| 3 |
Correct |
162 ms |
95316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
83916 KB |
Output is correct |
| 2 |
Runtime error |
259 ms |
131072 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
454 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
464 ms |
131072 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
