oj.uz

Submission #864534

# Submission time Handle Problem Language Result Execution time Memory
864534 2023-10-23T07:31:31 Z HuyQuang_re_Zero Islands (IOI08_islands) C++14
100 / 100
 592 ms 111024 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 nxt[N],w[N],deg[N];
bool visited[N];
ll n,i,u,v,k,sum,res;
ll f[N],ma0[N],ma1[N];
const ll oo=round(1e18);
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); deg[v]++;
        w[u]=k;
    }
    for(u=1;u<=n;u++)
        if(visited[u]==0)
        {
            queue <int> q;
            vector <int> node;
            ll local_res=0,ncycle=0,ma=-oo;
            vector <ll> c,dis; c.push_back(0); dis.push_back(0);
            q.push(u); visited[u]=1;
            while(q.size()>0)
            {
                int u=q.front(); q.pop();
                node.push_back(u);
                for(int v:a[u]) if(visited[v]==0) q.push(v),visited[v]=1;
                if(visited[nxt[u]]==0) q.push(nxt[u]),visited[nxt[u]]=1;
            }

            for(int u:node)
                if(deg[u]==0) q.push(u);
            while(q.size()>0)
            {
                int u=q.front(),v=nxt[u]; q.pop();
                ll k=f[u]+w[u];
                f[v]=max(f[v],k);
                if(ma0[v]<k) ma0[v]=k;
                if(ma1[v]<ma0[v]) swap(ma0[v],ma1[v]);
                deg[v]--;
                if(deg[v]==0) q.push(v);
            }

            int x=0,u;
            for(int u:node)
                if(deg[u]>0) { x=u; break; }
            for(int u:node) local_res=max(local_res,ma0[u]+ma1[u]);

            ///////////////////////////////////////////////////////////////////


            u=x;
            ll sum=0;
            ncycle++;
            c.push_back(u); dis.push_back(sum);
            sum+=w[u]; u=nxt[u];
            while(u!=x)
            {
                ncycle++;
                c.push_back(u); dis.push_back(sum);
                sum+=w[u]; u=nxt[u];
            }



            ////////////////////////////////////////////////////////////////////////////////

            for(i=1;i<=ncycle;i++)
            {
                u=c[i];
                c[i]=f[u];
            }
            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) local_res=max(local_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]);
                }
                local_res=max(local_res,c[i]-dis[i]+ma);
            }

            res+=local_res;
        }
    cout<<res;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB Output is correct
2 Correct 7 ms 31068 KB Output is correct
3 Correct 11 ms 23896 KB Output is correct
4 Correct 10 ms 23900 KB Output is correct
5 Correct 10 ms 23988 KB Output is correct
6 Correct 12 ms 24924 KB Output is correct
7 Correct 6 ms 31068 KB Output is correct
8 Correct 8 ms 31068 KB Output is correct
9 Correct 6 ms 31068 KB Output is correct
10 Correct 6 ms 31064 KB Output is correct
11 Correct 7 ms 31068 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32180 KB Output is correct
2 Correct 18 ms 33536 KB Output is correct
3 Correct 21 ms 25500 KB Output is correct
4 Correct 14 ms 24668 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34492 KB Output is correct
2 Correct 28 ms 38412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 41628 KB Output is correct
2 Correct 58 ms 51384 KB Output is correct
3 Correct 69 ms 55492 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 56876 KB Output is correct
2 Correct 115 ms 68040 KB Output is correct
3 Correct 116 ms 71004 KB Output is correct
4 Correct 147 ms 83132 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 59388 KB Output is correct
2 Correct 388 ms 91064 KB Output is correct
3 Correct 177 ms 75400 KB Output is correct
4 Correct 231 ms 90544 KB Output is correct
5 Correct 233 ms 88576 KB Output is correct
6 Correct 555 ms 90032 KB Output is correct
7 Correct 238 ms 111024 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 103380 KB Output is correct
2 Correct 230 ms 103544 KB Output is correct
3 Correct 214 ms 105696 KB Output is correct
4 Correct 312 ms 83484 KB Output is correct
5 Correct 219 ms 97868 KB Output is correct
6 Correct 237 ms 98560 KB Output is correct
7 Correct 592 ms 99376 KB Output is correct