oj.uz

Submission #864498

# Submission time Handle Problem Language Result Execution time Memory
864498 2023-10-23T05:35:13 Z HuyQuang_re_Zero Islands (IOI08_islands) C++14
90 / 100
 795 ms 131072 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
vector <int> a[N];
int tr[N],trc[N],cycle[N],nxt[N],w[N];
bool incycle[N],visited[N];
ll n,i,u,v,k,c[N],dis[N],ncycle,sum,res;
const ll oo=round(1e18);

void dfs(int u)
{
    visited[u]=1;
    auto consider=[&](int v)
    {
        if(visited[v]==0) dfs(v);
    };
    for(int adj:a[u]) consider(adj);
    consider(nxt[u]);
}

void Find_cycle(int u,int x)
{
    auto consider=[&](int v,int From)
    {
        if(From==x) return;
      //  if(adj==x) cerr<<adj<<'\n';
        int k=w[From];
    //    if(u==23) cerr<<v<<" "<<From<<" "<<tr[v'\n';
        if(tr[v]==0)
        {
            tr[v]=u; trc[v]=k;
            Find_cycle(v,From);
        }
        else if(ncycle==0)
        {
            sum=0;
           // cerr<<u<<' '<<v<<" "<<From<<" "<<x<<'\n';
            while(u!=v)
            {
            //    if(u>0) cerr<<u<<" "<<tr[23]<<'\n';
                cycle[++ncycle]=u; incycle[u]=1;
                dis[ncycle]=sum; sum+=trc[u];
                u=tr[u];
            }
            cycle[++ncycle]=u; incycle[u]=1;
            dis[ncycle]=sum; sum+=k;
            return ;
        }
    };
    for(int adj:a[u])
    {
        consider(adj,adj);
        if(ncycle>0) return ;
    }
    consider(nxt[u],u);
}


/////////////////////////////////////////////////////////////////////////////
ll cal(int u,int p,ll &ma)
{
    ll res=0,ma0=0,ma1=0;
    auto consider=[&](int adj,int From)
    {
        int v=adj;
        if(v!=p && incycle[v]==0)
        {
            ll k=cal(v,u,ma)+w[From];
            res=max(res,k);
            if(ma0<k) ma0=k;
            if(ma1<ma0) swap(ma1,ma0);
        }
    };
    for(int adj:a[u]) consider(adj,adj);
    consider(nxt[u],u);
    ma=max(ma,ma0+ma1);
    return res;
}
ll Work()
{
    int i,u,v;
    ll res=0,ma=-oo;
    for(i=1;i<=ncycle;i++)
    {
        u=cycle[i];
        c[i]=cal(u,0,res);
    }
    deque <int> dq;
    int j=1;
    for(i=1;i<ncycle;i++)
    {
        while(j<ncycle && sum-dis[j+1]+dis[i]>=dis[j+1]-dis[i])
        {
            j++;
            while(dq.size()>0 && c[dq.back()]-dis[dq.back()]<c[j]-dis[j])
                dq.pop_back();
            dq.push_back(j);
        }
        if(dq.size()>0 && dq.front()==i) dq.pop_front();
        if(dq.size()>0) res=max(res,c[i]+c[dq.front()]+sum+dis[i]-dis[dq.front()]);
    }

    j=ncycle+1;
    for(i=ncycle-1;i>=1;i--)
    {
        while(j-1>i && sum-dis[j-1]+dis[i]<dis[j-1]-dis[i])
        {
            j--;
            ma=max(ma,c[j]+dis[j]);
        }
        res=max(res,c[i]-dis[i]+ma);
    }
    return res;
}
int main()
{
  //  freopen("islands.inp","r",stdin);
  //  freopen("islands.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(u=1;u<=n;u++)
    {
        cin>>v>>k;
        nxt[u]=v; a[v].push_back(u);
        w[u]=k;
    }
    for(u=1;u<=n;u++)
        if(visited[u]==0)
        {
          //  cerr<<u<<'\n';
            dfs(u);
       //     cerr<<u<<'\n';
            tr[u]=-1;
            ncycle=0;
            Find_cycle(u,0);
          //  cerr<<u<<'\n';
            res+=Work();
        }
    cout<<res;
}

Compilation message

islands.cpp: In function 'long long int Work()':
islands.cpp:94:13: warning: unused variable 'v' [-Wunused-variable]
   94 |     int i,u,v;
      |             ^

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38232 KB Output is correct
2 Correct 7 ms 38236 KB Output is correct
3 Correct 7 ms 38236 KB Output is correct
4 Correct 7 ms 38236 KB Output is correct
5 Correct 7 ms 38236 KB Output is correct
6 Correct 7 ms 38236 KB Output is correct
7 Correct 7 ms 38236 KB Output is correct
8 Correct 7 ms 38236 KB Output is correct
9 Correct 7 ms 38236 KB Output is correct
10 Correct 7 ms 38236 KB Output is correct
11 Correct 7 ms 38236 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38236 KB Output is correct
2 Correct 7 ms 38384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 38488 KB Output is correct
2 Correct 8 ms 38424 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 38748 KB Output is correct
2 Correct 16 ms 40028 KB Output is correct
3 Correct 13 ms 38748 KB Output is correct
4 Correct 9 ms 38492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 40736 KB Output is correct
2 Correct 29 ms 41772 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 43348 KB Output is correct
2 Correct 62 ms 55468 KB Output is correct
3 Correct 71 ms 59208 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 52328 KB Output is correct
2 Correct 123 ms 72256 KB Output is correct
3 Correct 146 ms 88400 KB Output is correct
4 Correct 157 ms 99052 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 50684 KB Output is correct
2 Correct 452 ms 110928 KB Output is correct
3 Correct 190 ms 61780 KB Output is correct
4 Correct 224 ms 94544 KB Output is correct
5 Correct 233 ms 91984 KB Output is correct
6 Correct 795 ms 65516 KB Output is correct
7 Correct 258 ms 131072 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -