oj.uz

답안 #262228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
262228 2020-08-12T13:50:06 Z evpipis Islands (IOI08_islands) C++11
100 / 100
 1280 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int len = 1e6+5;
int deg[len], n, ccs;
ii par[len];
ll dep[len], best[len];
ll val[2*len], pref[2*len];
vector<int> order[len];
vector<ii> adj[len];

void dfs1(int u, int col){
    while (deg[u] == 2){
        deg[u] = 1;
        order[col].pb(u);

        u = par[u].fi;
    }
}

void find_spec(){
    queue<int> myq;
    for (int i = 1; i <= n; i++){
        deg[i] = adj[i].size();
        if (deg[i] == 1)
            myq.push(i);
    }

    while (!myq.empty()){
        int u = myq.front(), p = par[u].fi;
        myq.pop();

        deg[p]--, deg[u]--;
        if (deg[p] == 1)
            myq.push(p);
    }

    ccs = 0;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 2)
            dfs1(i, ccs++);

    /*printf("ccs = %d\n", ccs);
    for (int i = 0; i < ccs; i++){
        printf("cc#%d:", i);
        for (auto u: order[i])
            printf(" %d", u);
        printf("\n");
    }*/
}

ll dfs2(int st){
    vector<int> vec;
    stack<int> mys;
    mys.push(st);
    while (!mys.empty()){
        int u = mys.top();
        mys.pop();

        vec.pb(u);

        for (auto v: adj[u])
            if (v.fi != par[u].fi && !deg[v.fi])
                mys.push(v.fi);
    }

    ll ans = 0;
    reverse(vec.begin(), vec.end());
    for (auto u: vec){
        ll mx1 = 0, mx2 = 0;

        for (auto v: adj[u]){
            if (v.fi == par[u].fi || deg[v.fi])
                continue;

            dep[u] = max(dep[u], dep[v.fi]+v.se);

            if (dep[v.fi]+v.se > mx1)
                swap(mx1, mx2), mx1 = dep[v.fi]+v.se;
            else if (dep[v.fi]+v.se > mx2)
                mx2 = dep[v.fi]+v.se;
        }

        ans = max(ans, mx1+mx2);
    }

    return ans;
}

void find_diam(){
    for (int i = 0; i < ccs; i++)
        for (auto u: order[i])
            best[i] = max(best[i], dfs2(u));

    //for (int i = 0; i < ccs; i++)
      //  printf("best_without_specs[%d] = %lld\n", i, best[i]);
}

ll path(vector<int> &vec){
    ll ans = 0;

    int m = vec.size();
    for (int i = 0; i < 2*m; i++)
        val[i] = dep[vec[i%m]];
    for (int i = 0; i < 2*m-1; i++)
        pref[i+1] = pref[i]+par[vec[i%m]].se;

    deque<int> deq;
    for (int i = 0; i < 2*m; i++){
        while (!deq.empty() && i-deq.front()+1 > m)
            deq.pop_front();

        if (!deq.empty())
            ans = max(ans, pref[i]+val[i] + val[deq.front()]-pref[deq.front()]);

        while (!deq.empty() && val[i]-pref[i] >= val[deq.back()]-pref[deq.back()])
            deq.pop_back();
        deq.push_back(i);
    }

    return ans;
}

void find_path(){
    for (int i = 0; i < ccs; i++)
        best[i] = max(best[i], path(order[i]));

    //for (int i = 0; i < ccs; i++)
      //  printf("best_final[%d] = %lld\n", i, best[i]);
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        int p, c;
        scanf("%d %d", &p, &c);
        adj[i].pb(mp(p, c));
        adj[p].pb(mp(i, c));
        par[i] = mp(p, c);
    }

    find_spec();

    find_diam();

    find_path();

    ll ans = 0;
    for (int i = 0; i < ccs; i++)
        ans += best[i];
    printf("%lld\n", ans);
    return 0;
}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
islands.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  143 |         scanf("%d %d", &p, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47352 KB Output is correct
2 Correct 29 ms 47360 KB Output is correct
3 Correct 28 ms 47360 KB Output is correct
4 Correct 28 ms 47360 KB Output is correct
5 Correct 32 ms 47232 KB Output is correct
6 Correct 28 ms 47360 KB Output is correct
7 Correct 29 ms 47360 KB Output is correct
8 Correct 29 ms 47360 KB Output is correct
9 Correct 29 ms 47360 KB Output is correct
10 Correct 28 ms 47360 KB Output is correct
11 Correct 29 ms 47352 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 47360 KB Output is correct
2 Correct 29 ms 47360 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 47480 KB Output is correct
2 Correct 42 ms 47608 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 48256 KB Output is correct
2 Correct 68 ms 49940 KB Output is correct
3 Correct 47 ms 48632 KB Output is correct
4 Correct 38 ms 47992 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 51064 KB Output is correct
2 Correct 90 ms 53680 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 59588 KB Output is correct
2 Correct 167 ms 61400 KB Output is correct
3 Correct 192 ms 67568 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 70264 KB Output is correct
2 Correct 316 ms 83192 KB Output is correct
3 Correct 424 ms 85284 KB Output is correct
4 Correct 438 ms 98924 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 454 ms 110420 KB Output is correct
2 Correct 1024 ms 119776 KB Output is correct
3 Correct 471 ms 94148 KB Output is correct
4 Correct 623 ms 116028 KB Output is correct
5 Correct 642 ms 117408 KB Output is correct
6 Correct 1128 ms 105456 KB Output is correct
7 Correct 742 ms 127912 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 571 ms 102272 KB Output is correct
2 Correct 497 ms 102300 KB Output is correct
3 Correct 783 ms 131072 KB Output is correct
4 Correct 763 ms 125152 KB Output is correct
5 Correct 594 ms 131072 KB Output is correct
6 Correct 521 ms 118432 KB Output is correct
7 Correct 1280 ms 119432 KB Output is correct