Submission #510154

#	Time	Username	Problem	Language	Result	Execution time	Memory
510154		Yazan_Alattar	Islands (IOI08_islands)	C++14	0 / 100	2087 ms	131076 KiB

islands

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <utility>
#include <cmath>
#include <numeric>
#include <assert.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1000007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

vector < pair < ll, pair <int,int> > > edges;
vector < pair <int,ll> > adj[M];
vector <int> nodes;
pair <int,int> edge;
ll n, cost[M], mxchild[M], p[M], ans, edgecost, root, timer;
bool vist[M];

void get(int node)
{
    ++timer;
    nodes.pb(node);
    vist[node] = 1;
    for(auto i : adj[node]){
        edges.pb({i.S, {node, i.F}});
        if(!vist[i.F]) get(i.F);
    }
    return;
}

void dfs(int node, ll cur)
{
//    cout << node << " " << edge.F << " " << edge.S << endl;
    ++timer;
    cost[node] = cur;
    mxchild[node] = cur;
    for(auto i : adj[node]){
        if(i.F == p[node] || ((edge == make_pair(node, i.F) || edge == make_pair(i.F, node)) && edgecost == i.S)) continue;
        p[i.F] = node;
        dfs(i.F, cur + i.S);
        mxchild[node] = max(mxchild[node], mxchild[i.F]);
    }
    return;
}

pair <int,int> calc(int node)
{
    ++timer;
    pair <ll,ll> ret;
    int cur = node;
    while(p[cur] != root) cur = p[cur];
    ret.F = cost[node] - cost[cur];
    ret.S = mxchild[node];
    return ret;
}

ll best(int node)
{
    ll ret = 0;
    for(auto i : adj[node]){
        if(i.F == p[node]) continue;
        if(i.F == edge.F || i.F == edge.S) return -1;
        ll x = best(i.F);
        if(x == -1 && node != 1) return -1;
        else ret = max(ret, best(i.F));
    }
    return ret;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        ll x, y;
        cin >> x >> y;
//        x = (i % n) + 1;
//        y = i;
        adj[x].pb({i, y});
        adj[i].pb({x, y});
    }
    for(int j = 1; j <= n; ++j){
        if(vist[j]) continue;
        timer = 0;
        get(j);
        sort(all(edges), greater < pair < ll, pair <int,int> > > ());
        edge = {edges.back().S.F, edges.back().S.S};
        edgecost = edges.back().F;
        root = 0;
        for(auto i : nodes) if(i != edge.F && i != edge.S) {root = i; break;}
        if(root == 0){
//            for(auto i : edges) cout << i.S.F << " " << i.S.S << " " << i.F << endl;
            ans += edges[0].F;
            continue;
        }
        dfs(root, 0);
        ll mx1 = 0, mx2 = 0, mx = 0;
        for(auto i : nodes){
            if(cost[i] > mx1) mx2 = mx1, mx1 = cost[i];
            else if(cost[i] > mx2) mx2 = cost[i];
        }
        mx = mx1 + mx2;
        mx1 = best(root);
        pair <ll,ll> nodea = calc(edge.F);
        pair <ll,ll> nodeb = calc(edge.S);
        mx = max(mx, nodea.F + nodeb.S + edges.back().F);
        mx = max(mx, nodea.F + nodeb.F + edges.back().F);
        mx = max(mx, nodea.S + nodeb.F + edges.back().F);
        mx = max(mx, nodea.S + nodeb.S + edges.back().F);
        mx = max(mx, mx1 + cost[edge.F] + nodeb.S + edges.back().F);
        mx = max(mx, mx1 + cost[edge.F] + nodeb.F + edges.back().F);
        mx = max(mx, mx1 + nodea.F + cost[edge.S] + edges.back().F);
        mx = max(mx, mx1 + nodea.S + cost[edge.S] + edges.back().F);
        ans += mx;
        edges.clear();
        nodes.clear();
    }
    assert(timer > 1e7);
    cout << ans << endl;
    return 0;
}

• Subtask 1: 0 / 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