Submission #506106

# Submission time Handle Problem Language Result Execution time Memory
506106 2022-01-11T15:45:40 Z blue Islands (IOI08_islands) C++17
70 / 100
753 ms 131076 KB
#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 = 1'000'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);
    }
}






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), dist2(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]);

        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;
        }
    }

    // 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, dist2[u]);

        for(pii v: edge[u])
        {
            if((cyclic[v.first] && cyclic[u]) || visit2[v.first]) continue;
            visit2[v.first] = 1;
            dist2[v.first] = dist2[u] + v.second;
            tbv.push(v.first);
        }
    }

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

    return res;
}







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

ll fwd_dist(int u, int v)
{
    if(x[u] <= x[v]) return x[v] - x[u];
    else return tot - x[u] + x[v];
}









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);

    for(int i = 0; i < z; i++)
    {
        ring.push_back(ring[i]);
        outer.push_back(outer[i]);
    }
    // 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];

    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]);
    }

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

}
# Verdict Execution time Memory Grader output
1 Correct 47 ms 92300 KB Output is correct
2 Correct 37 ms 92212 KB Output is correct
3 Correct 37 ms 92364 KB Output is correct
4 Correct 37 ms 92228 KB Output is correct
5 Correct 40 ms 92252 KB Output is correct
6 Correct 37 ms 92224 KB Output is correct
7 Correct 43 ms 92280 KB Output is correct
8 Correct 41 ms 92204 KB Output is correct
9 Correct 36 ms 92240 KB Output is correct
10 Correct 37 ms 92232 KB Output is correct
11 Correct 37 ms 92212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 38 ms 92364 KB Output is correct
2 Correct 38 ms 92320 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 45 ms 92264 KB Output is correct
2 Correct 43 ms 92704 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 51 ms 93180 KB Output is correct
2 Correct 70 ms 96044 KB Output is correct
3 Correct 66 ms 93180 KB Output is correct
4 Correct 46 ms 92680 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 84 ms 97272 KB Output is correct
2 Correct 131 ms 98928 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 194 ms 103964 KB Output is correct
2 Correct 248 ms 111524 KB Output is correct
3 Correct 320 ms 128256 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 376 ms 110592 KB Output is correct
2 Runtime error 392 ms 131076 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 712 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 753 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -