oj.uz

답안 #510132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
510132 2022-01-14T18:02:33 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;
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] != 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};
        edgecost = edges.back().F;
        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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2094 ms 23756 KB Time limit exceeded
2 Execution timed out 2091 ms 23756 KB Time limit exceeded
3 Incorrect 12 ms 23884 KB Output isn't correct
4 Execution timed out 2094 ms 23756 KB Time limit exceeded
5 Runtime error 59 ms 131076 KB Execution killed with signal 9
6 Execution timed out 2087 ms 23776 KB Time limit exceeded
7 Execution timed out 2074 ms 23756 KB Time limit exceeded
8 Execution timed out 2088 ms 23812 KB Time limit exceeded
9 Execution timed out 2081 ms 23756 KB Time limit exceeded
10 Execution timed out 2078 ms 23756 KB Time limit exceeded
11 Execution timed out 2088 ms 23756 KB Time limit exceeded

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 24012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 31472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2057 ms 49388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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