Submission #1037614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037614		8pete8	Islands (IOI08_islands)	C++17	70 / 100	472 ms	131072 KiB

islands

#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,z=0;
vector<pair<int,ll>>adj[mxn+10];
int have=0;
pii up[mxn+10];
ll dp1[mxn+10],mx;
bitset<mxn+10>on,vis;
queue<pii>q;
void dfs(int cur,int p){//fake dfs
    q.push({cur,-1});
    while(!q.empty()){
        cur=q.front().f,p=q.front().s;
        q.pop();
        if(vis[cur])continue;
        vis[cur]=1;
        for(auto i:adj[cur]){
            if(i.f==p)continue;
            if(vis[i.f]&&!have){
                x=cur,y=i.f,z=i.s;
                have++;
            }
            if(!vis[i.f])q.push({i.f,cur});
        }
    }
}
void dfs1(int cur,int p){//dont take edge x,y
    vector<ll>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 
ll pref[mxn+10],suf[mxn+10];
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});
    }
    ll ans=0;
    vector<pii>cycle;
    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
            cycle.clear();
            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));
            pref[0]=0,suf[cycle.size()-1]=0;
            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 (stderr)

islands.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
islands.cpp:43:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   43 | void dfs(int cur,int p){//fake dfs
      |                       ^
islands.cpp:60:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   60 | void dfs1(int cur,int p){//dont take edge x,y
      |                        ^
islands.cpp:78:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   78 | int32_t main(){
      |              ^
islands.cpp: In function 'int32_t main()':
islands.cpp:111:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             for(int i=1;i<cycle.size();i++)pref[i]=cycle[i].s+pref[i-1];
      |                         ~^~~~~~~~~~~~~
islands.cpp:117:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             for(int i=0;i<cycle.size();i++){
      |                         ~^~~~~~~~~~~~~
islands.cpp:123:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |                 if(i+1<cycle.size())suf[i]=max(suf[i],suf[i+1]);
      |                    ~~~^~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10