Submission #1036154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036154		12345678	Islands (IOI08_islands)	C++17	21 / 100	2050 ms	131072 KiB

islands

#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;

#define ll long long

int vs[nx], n, x, cnt, rt;
ll w, mx[nx], pw[nx], ans;
vector<tuple<int, int, ll>> d[nx];
vector<pair<int, ll>> c;

bool dfs(int u, int pidx)
{
    vs[u]=1;
    for (auto [v, idx, w]:d[u])
    {
        if (idx==pidx) continue;
        if (!vs[v]) 
        {
            pw[v]=w;
            //cout<<"here "<<u<<' '<<v<<' '<<w<<'\n', 
            if (dfs(v, u)) vs[u]=2; 
        }
        else if (vs[v]==1) pw[v]=w, vs[u]=2, rt=v;
    }
    if (vs[u]==2) c.push_back({u, pw[u]});
    if (vs[u]==2&&u!=rt) return 1;
    return 0;
}

void dfs2(int u, int pidx)
{
    for (auto [v, idx, w]:d[u]) if (idx!=pidx&&vs[v]==1) dfs2(v, idx), mx[u]=max(mx[u], mx[v]+w);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>x>>w, d[i].push_back({x, i, w}), d[x].push_back({i, i, w});
    for (int i=1; i<=n; i++) 
    {
        if (!vs[i]) 
        {
            c.clear();
            dfs(i, -1);
            for (auto [u, p]:c) dfs2(u, -1);
            //for (auto x:c) cout<<"cy "<<x.first<<' '<<x.second<<'\n';
            reverse(c.begin(), c.end());
            for (int i=2; i<c.size(); i++) c[i].second+=c[i-1].second;
            ll sm=c[0].second+c[c.size()-1].second, tmp=0;
            c[0].second=0;
            //for (auto x:c) cout<<"cy "<<x.first<<' '<<x.second<<'\n';
            //cout<<"sm "<<sm<<'\n';
            for (int j=0; j<c.size(); j++)
            {
                for (int k=j+1; k<c.size(); k++)
                {
                    tmp=max(tmp, mx[c[j].first]+mx[c[k].first]+max(c[k].second-c[j].second, sm-(c[k].second-c[j].second)));
                }
            }
            //cout<<"debug "<<i<<' '<<tmp<<'\n';
            ans+=tmp;
        }
    }
    cout<<ans;
}

Compilation message (stderr)

islands.cpp: In function 'int main()':
islands.cpp:52:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int i=2; i<c.size(); i++) c[i].second+=c[i-1].second;
      |                           ~^~~~~~~~~
islands.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int j=0; j<c.size(); j++)
      |                           ~^~~~~~~~~
islands.cpp:59:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 for (int k=j+1; k<c.size(); k++)
      |                                 ~^~~~~~~~~

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