Submission #506117

#	Time	Username	Problem	Language	Result	Execution time	Memory
506117		blue	Islands (IOI08_islands)	C++17	70 / 100	631 ms	131072 KiB

islands

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<int>;
using vvll = vector<vll>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int maxN = 600'000;

int N;
vi A(1+maxN);
vi L(1+maxN);
vector<pii>* edge = new vector<pii>[1+maxN];








int ct = 0;
vi cc(1+maxN, 0);
vi cc_list[1+maxN];

void dfs1(int u)
{
    cc[u] = ct;
    cc_list[cc[u]].push_back(u);
    for(pii v: edge[u])
    {
        if(cc[v.first]) continue;
        dfs1(v.first);
    }
    if(!cc[A[u]]) dfs1(A[u]);
}






vector<short> cyclic(1+maxN, 1);
vi indegree(1+maxN, 0);


int tree_ct;

vector<short> visit1(1+maxN, 0), visit2(1+maxN, 0);
vll dist1(1+maxN, 0);

vll depth(1+maxN, 0);

ll find_tree_diameter(int src)
{
    // cerr << "\n calling find tree diameter from " << src << '\n';
    queue<int> tbv;
    tbv.push(src);
    visit1[src] = 1;

    int opp = src;

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();
        depth[src] = max(depth[src], dist1[u]);

        edge[u].push_back({A[u], L[u]});
        for(pii v: edge[u])
        {
            if((cyclic[v.first] && cyclic[u]) || visit1[v.first]) continue;
            visit1[v.first] = 1;
            dist1[v.first] = dist1[u] + v.second;
            tbv.push(v.first);

            if(dist1[v.first] > dist1[opp]) opp = v.first;
        }
        edge[u].pop_back();

        dist1[u] = 0;
    }

    // cerr << "opp = " << opp << '\n';


    ll res = 0;

    tbv.push(opp);
    visit2[opp] = 1;

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();
        // cerr << "bfs2: " << u << '\n';

        res = max(res, dist1[u]);

        edge[u].push_back({A[u], L[u]});
        for(pii v: edge[u])
        {
            if((cyclic[v.first] && cyclic[u]) || visit2[v.first]) continue;
            visit2[v.first] = 1;
            dist1[v.first] = dist1[u] + v.second;
            tbv.push(v.first);
        }
        edge[u].pop_back();
    }

    // cerr << "tree diam from " << src << " = " << res << '\n';

    return res;
}







int z;
vll ring, outer, x;
ll tot;







ll solve(vi lst)
{
    // cerr << "calling solve: ";
    // for(int u: lst) cerr << u << ' ';
    // cerr << '\n';

    queue<int> tbv;
    for(int u: lst) if(!indegree[u]) tbv.push(u);

    while(!tbv.empty())
    {
        int u = tbv.front();
        tbv.pop();
        cyclic[u] = 0;
        indegree[A[u]]--;
        if(!indegree[A[u]]) tbv.push(A[u]);
    }

    ll tree_diam = 0;


    ring.clear();
    outer.clear();

    // cerr << "A\n";

    int r = 0;

    for(int u: lst)
    {
        if(!cyclic[u]) continue;

        if(!r) r = u;

        tree_ct++;
        tree_diam = max(tree_diam, find_tree_diameter(u));
    }

    // cerr << "B\n";

    int y = r;
    while(1)
    {
        ring.push_back(L[y]);
        outer.push_back(depth[y]);

        y = A[y];
        if(y == r) break;
    }

    z = sz(ring);
    // cerr << "component: \n";
    //
    // for(int i = 0; i < z; i++) cerr << ring[i] << ' ' << outer[i] << "\n";
    //
    // cerr << "\n\n";
    //
    // cerr << "C\n";



    x = vll(2*z, 0);
    for(int i = 1; i < 2*z; i++) x[i] = x[i-1] + ring[(i-1)%z];

    tot = x[z];

    multiset<ll> val;

    ll res = 0;

    // cerr << "D\n";
    // cerr << z << '\n';

    for(int i = 0; i < z-1; i++)
    {
        // cerr << i << " : initially inserting " << -x[i] + outer[i] << '\n';
        val.insert(-x[i] + outer[i%z]);
    }

    // cerr << "#\n";
    for(int i = z-1; i < 2*z; i++)
    {
        // cerr << i << '\n';
        res = max(res, x[i] + outer[i%z] + *val.rbegin());
        // cerr << "p\n";
        val.insert(-x[i] + outer[i%z]);
        // cerr << "q\n";
        val.erase(val.find(-x[i-z+1] + outer[(i-z+1)%z]));
        // cerr << "r\n";
    }



    // int x

    // cerr << "tree diameter = " << tree_diam << '\n';









    // cerr << "E\n";






    // cerr << "return value 1: " << tree_diam << ' ' << res << '\n';

    return max(tree_diam, res);
}







int main()
{











    cin >> N;
    for(int i = 1; i <= N; i++)
    {
        cin >> A[i] >> L[i];
        // edge[i].push_back({A[i], L[i]});
        edge[A[i]].push_back({i, L[i]});

        indegree[A[i]]++;
    }













    for(int i = 1; i <= N; i++)
    {
        if(cc[i]) continue;
        ct++;
        dfs1(i);
    }




    ll ans = 0;

    for(int c = 1; c <= ct; c++) ans += solve(cc_list[c]);


    cout << ans << '\n';

}

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