oj.uz

Submission #1038056

# Submission time Handle Problem Language Result Execution time Memory
1038056 2024-07-29T12:33:46 Z 8pete8 Islands (IOI08_islands) C++17
100 / 100
 700 ms 120528 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,z=0;
vector<pair<int,ll>>adj[mxn+10];
int have=0,pointer=0;
int up[mxn+10],dup[mxn+10];
pii cycle[mxn+10];
ll dp1[mxn+10],mx,suf[mxn+10];
//8^106
bitset<mxn+10>on,vis;
ll ans=0,pref=0,prefmx=0;
queue<pii>q;
map<pii,int>mp;
ll m1=0,m2=0;
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
    q.push({cur,-1});
    while(!q.empty()){
        cur=q.front().f,p=q.front().s;
        q.pop();
        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;
            dup[i.f]=i.s;
            dp1[i.f]=dp1[cur]+1;
            q.push({i.f,cur});
        }
        cycle[pointer++]={dp1[cur],cur};
        dp1[cur]=0;
    }
}
//find diameter 
int32_t main(){
    fastio
    cin>>n;
    for(int i=1;i<=n;i++)cin>>cycle[i].f>>cycle[i].s;
    for(int i=1;i<=n;i++){
        if(cycle[i].f==-1){
            cycle[i]={0,0};
            continue;
        }
        if(cycle[cycle[i].f].f==i){
            cycle[cycle[i].f].f=-1;
            cycle[i].s=max(cycle[i].s,cycle[cycle[i].f].s);
        }
        adj[i].pb({cycle[i].f,cycle[i].s});
        adj[cycle[i].f].pb({i,cycle[i].s});
        cycle[i]={0,0};
    }
    /*
    for(auto i:mp){
        adj[i.f.f].pb({i.f.s,i.s});
        adj[i.f.s].pb({i.f.f,i.s});
    }*/
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        have=0,z=0,x=i,mx=0;
        dfs(i,-1);
        pointer=0;
        dfs1(x,-1);
        sort(cycle,cycle+pointer);
        reverse(cycle,cycle+pointer);
        for(int j=0;j<pointer;j++){
            dp1[up[cycle[j].s]]=max(dp1[up[cycle[j].s]],dp1[cycle[j].s]+dup[cycle[j].s]);
            mx=max(mx,dp1[cycle[j].s]);
            m1=m2=0;
            for(auto k:adj[cycle[j].s]){
                if(k.f==up[cycle[j].s])continue;
                if(cycle[j].s==x&&k.f==y)continue;
                if(cycle[j].s==y&&k.f==x)continue;
                if(dp1[k.f]+k.s>=m1)m2=m1,m1=dp1[k.f]+k.s;
                else if(dp1[k.f]+k.s>=m2)m2=dp1[k.f]+k.s;
            }
            mx=max(mx,m1+m2);
        }
        if(have){
            pointer=0;
            while(y!=x){
                cycle[pointer++]={y,dup[y]};
                on[y]=1;
                y=up[y];
            }
            cycle[pointer++]={x,0};
            on[x]=1;
            reverse(cycle,cycle+pointer);
            suf[pointer-1]=0;
            pref=0,prefmx=0;
            for(int i=pointer-2;i>=0;i--)suf[i]=cycle[i+1].s+suf[i+1];
            for(int i=0;i<pointer;i++){
                dp1[cycle[i].f]=0;
                for(auto j:adj[cycle[i].f])if(!on[j.f])dp1[cycle[i].f]=max(dp1[cycle[i].f],dp1[j.f]+j.s);
            }
            for(int i=pointer-1;i>=0;i--){
                suf[i]=suf[i]+dp1[cycle[i].f];
                if(i+1<pointer)suf[i]=max(suf[i],suf[i+1]);
            }
            for(int i=0;i<pointer;i++){
                pref+=cycle[i].s;
                prefmx=max(prefmx,pref+dp1[cycle[i].f]);
                if(i+1<pointer)mx=max(mx,prefmx+suf[i+1]+z);
            }
        }
        ans+=mx;
    }
    cout<<ans<<'\n';
}

Compilation message

islands.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
islands.cpp:48:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   48 | void dfs(int cur,int p){//fake dfs
      |                       ^
islands.cpp:65:24: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 | void dfs1(int cur,int p){//dont take edge x,y
      |                        ^
islands.cpp:84:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   84 | int32_t main(){
      |              ^

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 34652 KB Output is correct
2 Correct 7 ms 34576 KB Output is correct
3 Correct 8 ms 34652 KB Output is correct
4 Correct 7 ms 32724 KB Output is correct
5 Correct 7 ms 34652 KB Output is correct
6 Correct 5 ms 34648 KB Output is correct
7 Correct 6 ms 34648 KB Output is correct
8 Correct 5 ms 34652 KB Output is correct
9 Correct 6 ms 34756 KB Output is correct
10 Correct 5 ms 32604 KB Output is correct
11 Correct 7 ms 32708 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 34652 KB Output is correct
2 Correct 7 ms 32796 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 34908 KB Output is correct
2 Correct 8 ms 34908 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 35420 KB Output is correct
2 Correct 15 ms 36700 KB Output is correct
3 Correct 11 ms 35932 KB Output is correct
4 Correct 8 ms 35160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 39260 KB Output is correct
2 Correct 24 ms 42212 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 48092 KB Output is correct
2 Correct 52 ms 49236 KB Output is correct
3 Correct 91 ms 51792 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 66128 KB Output is correct
2 Correct 111 ms 73168 KB Output is correct
3 Correct 129 ms 79700 KB Output is correct
4 Correct 179 ms 87124 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 104356 KB Output is correct
2 Correct 548 ms 109648 KB Output is correct
3 Correct 160 ms 92496 KB Output is correct
4 Correct 229 ms 105428 KB Output is correct
5 Correct 211 ms 105812 KB Output is correct
6 Correct 604 ms 102360 KB Output is correct
7 Correct 241 ms 108768 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 96208 KB Output is correct
2 Correct 226 ms 111696 KB Output is correct
3 Correct 241 ms 117840 KB Output is correct
4 Correct 200 ms 94036 KB Output is correct
5 Correct 221 ms 120528 KB Output is correct
6 Correct 278 ms 113484 KB Output is correct
7 Correct 700 ms 118100 KB Output is correct