oj.uz

Submission #510141

# Submission time Handle Problem Language Result Execution time Memory
510141 2022-01-14T18:09:37 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 = 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;
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)) && 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)
{
    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;
        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();
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 23756 KB Time limit exceeded
2 Execution timed out 2089 ms 23756 KB Time limit exceeded
3 Incorrect 15 ms 23940 KB Output isn't correct
4 Execution timed out 2083 ms 23808 KB Time limit exceeded
5 Runtime error 62 ms 131076 KB Execution killed with signal 9
6 Execution timed out 2091 ms 23756 KB Time limit exceeded
7 Execution timed out 2080 ms 23756 KB Time limit exceeded
8 Execution timed out 2095 ms 23756 KB Time limit exceeded
9 Execution timed out 2092 ms 23756 KB Time limit exceeded
10 Execution timed out 2060 ms 23756 KB Time limit exceeded
11 Execution timed out 2070 ms 23756 KB Time limit exceeded

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 23940 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 67 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 259 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 46 ms 31672 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 355 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 214 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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