oj.uz

답안 #506105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
506105 2022-01-11T15:44:03 Z blue Islands (IOI08_islands) C++17
70 / 100
 757 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);
    }
}






vi cyclic(1+maxN, 1);
vi indegree(1+maxN, 0);


int tree_ct;

vi 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';

}

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98144 KB Output is correct
2 Correct 40 ms 98168 KB Output is correct
3 Correct 40 ms 98192 KB Output is correct
4 Correct 39 ms 98116 KB Output is correct
5 Correct 39 ms 98104 KB Output is correct
6 Correct 42 ms 98100 KB Output is correct
7 Correct 40 ms 98064 KB Output is correct
8 Correct 43 ms 98168 KB Output is correct
9 Correct 41 ms 98160 KB Output is correct
10 Correct 44 ms 98108 KB Output is correct
11 Correct 40 ms 98056 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 98268 KB Output is correct
2 Correct 48 ms 98200 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 98252 KB Output is correct
2 Correct 44 ms 98628 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 99216 KB Output is correct
2 Correct 74 ms 102328 KB Output is correct
3 Correct 61 ms 99324 KB Output is correct
4 Correct 50 ms 98696 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 103848 KB Output is correct
2 Correct 129 ms 106060 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 112460 KB Output is correct
2 Correct 285 ms 119644 KB Output is correct
3 Correct 330 ms 131072 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 121808 KB Output is correct
2 Runtime error 366 ms 131076 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 636 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 757 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -