oj.uz

Submission #864459

# Submission time Handle Problem Language Result Execution time Memory
864459 2023-10-23T03:30:25 Z HuyQuang_re_Zero Islands (IOI08_islands) C++14
70 / 100
 431 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;
struct edge { int u,num,k; };
vector <edge> a[N];
ll tr[N],trc[N],n,i,u,v,k,c[N],dis[N],ncycle,cycle[N],d[N],sum,incycle[N],res,visited[N];
const ll oo=round(1e18);
struct Fenwick_Tree
{
    ll bit[N],d[N],n;
    void Init(int _n)
    {
        n=_n;
        for(int i=1;i<=n;i++) bit[i]=d[i]=-oo;
    }
    void update(int i,ll k)
    {
        d[i]=max(d[i],k);
        while(i<=n) bit[i]=max(bit[i],k),i+=(i & -i);
    }
    ll get(int l,int r)
    {
        ll res=-oo,i=r;
        while(i>=l)
            if(i-(i & -i)>=l) res=max(res,bit[i]),i-=(i & -i);
            else res=max(res,d[i]),i--;
        return res;
    }
} FT_sub,FT_sum;

void dfs(int u)
{
    visited[u]=1;
    for(edge adj:a[u])
    {
        int v=adj.u;
        if(visited[v]==0) dfs(v);
    }
}

void Find_cycle(int u,int x)
{
    for(edge adj:a[u])
    {
        if(adj.num==x) continue;
        int v=adj.u,k=adj.k;
        if(tr[v]==0)
        {
            tr[v]=u; trc[v]=k;
            Find_cycle(v,adj.num);
        }
        else if(ncycle==0)
        {
            sum=0;
            while(u!=v)
            {
                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 ;
        }
    }
}


/////////////////////////////////////////////////////////////////////////////
ll cal(int u,int p,ll &ma)
{
    ll res=0;
    vector <ll> vec;
    for(edge adj:a[u])
    {
        int v=adj.u;
        if(v!=p && incycle[v]==0)
        {
            ll k=cal(v,u,ma)+adj.k;
            res=max(res,k);
            vec.push_back(k);
        }
    }
    sort(vec.rbegin(),vec.rend());
    if(vec.size()>=2) ma=max(ma,vec[0]+vec[1]);
    return res;
}
ll Work()
{
    int i,u,v;
    FT_sub.Init(ncycle);
    FT_sum.Init(ncycle);
    ll res=0;
    for(i=1;i<=ncycle;i++)
    {
        u=cycle[i];
   //     cerr<<u<<" "<<sum<<'\n';
        c[i]=cal(u,0,res);
        FT_sub.update(i,c[i]-dis[i]);
        FT_sum.update(i,c[i]+dis[i]);
    }
    for(i=1;i<ncycle;i++)
    {
        int l=i,r=ncycle;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(sum-(dis[mid]-dis[i])>=dis[mid]-dis[i])
                l=mid;
            else r=mid-1;
        }
       // cerr<<c[i]-dis[i]+FT_sum.get(l+1,ncycle)<<'\n';
      //  cerr<<cycle[i]<<' '<<cycle[l]<<' '<<dis[i]<<'\n';
        res=max(res,max(c[i]+sum+dis[i]+FT_sub.get(i+1,l),c[i]-dis[i]+FT_sum.get(l+1,ncycle)));
    }
    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;
        a[u].push_back({ v,u,k }); a[v].push_back({ u,u,k });
    }
    for(u=1;u<=n;u++)
        if(visited[u]==0)
        {
            dfs(u);
            tr[u]=-1;
            ncycle=0;
            Find_cycle(u,0);
            res+=Work();
        }
    cout<<res;
}

Compilation message

islands.cpp: In function 'long long int Work()':
islands.cpp:103:13: warning: unused variable 'v' [-Wunused-variable]
  103 |     int i,u,v;
      |             ^
islands.cpp: In function 'int main()':
islands.cpp:141:26: warning: narrowing conversion of 'v' from 'long long int' to 'int' [-Wnarrowing]
  141 |         a[u].push_back({ v,u,k }); a[v].push_back({ u,u,k });
      |                          ^
islands.cpp:141:28: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
  141 |         a[u].push_back({ v,u,k }); a[v].push_back({ u,u,k });
      |                            ^
islands.cpp:141:30: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
  141 |         a[u].push_back({ v,u,k }); a[v].push_back({ u,u,k });
      |                              ^
islands.cpp:141:53: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
  141 |         a[u].push_back({ v,u,k }); a[v].push_back({ u,u,k });
      |                                                     ^
islands.cpp:141:55: warning: narrowing conversion of 'u' from 'long long int' to 'int' [-Wnarrowing]
  141 |         a[u].push_back({ v,u,k }); a[v].push_back({ u,u,k });
      |                                                       ^
islands.cpp:141:57: warning: narrowing conversion of 'k' from 'long long int' to 'int' [-Wnarrowing]
  141 |         a[u].push_back({ v,u,k }); a[v].push_back({ u,u,k });
      |                                                         ^

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45916 KB Output is correct
2 Correct 8 ms 45912 KB Output is correct
3 Correct 7 ms 45928 KB Output is correct
4 Correct 7 ms 45660 KB Output is correct
5 Correct 7 ms 45656 KB Output is correct
6 Correct 8 ms 45660 KB Output is correct
7 Correct 8 ms 45656 KB Output is correct
8 Correct 7 ms 45660 KB Output is correct
9 Correct 8 ms 45660 KB Output is correct
10 Correct 7 ms 45660 KB Output is correct
11 Correct 8 ms 45660 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45916 KB Output is correct
2 Correct 8 ms 45912 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45916 KB Output is correct
2 Correct 10 ms 48216 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48732 KB Output is correct
2 Correct 22 ms 50780 KB Output is correct
3 Correct 16 ms 48984 KB Output is correct
4 Correct 11 ms 48220 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 52060 KB Output is correct
2 Correct 39 ms 54364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 60680 KB Output is correct
2 Correct 91 ms 67664 KB Output is correct
3 Correct 116 ms 84328 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 74816 KB Output is correct
2 Correct 190 ms 109056 KB Output is correct
3 Correct 256 ms 115160 KB Output is correct
4 Runtime error 198 ms 131072 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 123176 KB Output is correct
2 Runtime error 431 ms 131072 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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