oj.uz

Submission #510129

# Submission time Handle Problem Language Result Execution time Memory
510129 2022-01-14T17:59:58 Z Yazan_Alattar Islands (IOI08_islands) C++14
0 / 100
 2000 ms 131076 KB 
#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 = 200007;
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;
bool vist[M];

void get(int node)
{
    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;
    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)) 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)
{
    pair <ll,ll> ret;
    int cur = node;
    while(p[cur] != 1) 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;
        adj[x].pb({i, y});
        adj[i].pb({x, y});
    }
    for(int j = 1; j <= n; ++j){
        if(vist[j]) continue;
        get(j);
        sort(all(edges), greater < pair < ll, pair <int,int> > > ());
        edge = {edges.back().S.F, edges.back().S.S};
        int 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();
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 4940 KB Time limit exceeded
2 Execution timed out 2048 ms 4940 KB Time limit exceeded
3 Incorrect 3 ms 5068 KB Output isn't correct
4 Execution timed out 2069 ms 4940 KB Time limit exceeded
5 Runtime error 69 ms 131076 KB Execution killed with signal 9
6 Execution timed out 2072 ms 4940 KB Time limit exceeded
7 Execution timed out 2083 ms 4940 KB Time limit exceeded
8 Execution timed out 2079 ms 4940 KB Time limit exceeded
9 Execution timed out 2079 ms 4940 KB Time limit exceeded
10 Execution timed out 2074 ms 4940 KB Time limit exceeded
11 Execution timed out 2077 ms 5020 KB Time limit exceeded

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 75 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 275 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 12640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 498 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 147 ms 29808 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 9932 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 11908 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -