제출 #114721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114721		zubec	Islands (IOI08_islands)	C++14	90 / 100	1740 ms	131072 KiB

islands

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 1000100;

int n;

ll ans = 0;

int len[N], nxt[N];

vector <int> g[N];

bool used[N], block[N];

int used2[N], pr[N], cEnd, cStrt, pr2[N];

int cId;

int getTo(int v, int id){
    return (v == id ? nxt[v] : id);
}

int fnd_cycle(int v, int p){
    used2[v] = 1;

    for (int i = 0; i < g[v].size(); i++){
        int id = g[v][i];
        int to = getTo(v, id);
        if (id == p)
            continue;
        if (used2[to] == 0){
            pr[to] = v;
            pr2[to] = id;
            if (fnd_cycle(to, id)){
                return 1;
            }
        } else
        if (used2[to] == 1){
            cEnd = v;
            cId = id;
            cStrt = to;
            return 1;
        }
    }

    used2[v] = 2;

    return 0;
}

ll dfs(int v, int p){
    used[v] = 1;
    ll curmx = 0;
    for (int i = 0; i < g[v].size(); i++){
        int id = g[v][i];
        int to = getTo(v, id);
        if (to == p)
            continue;
        curmx = max(curmx, dfs(to, v)+len[id]);
    }
    return curmx;
}

ll mx, mxver;

void dfs2(int v, int p, ll curlen){
    if (curlen > mx){
        mx = curlen;
        mxver = v;
    }
    for (int i = 0; i < g[v].size(); i++){
        int id = g[v][i];
        int to = getTo(v, id);
        if (!block[id] && to != p)
            dfs2(to, v, curlen+len[id]);
    }
}

ll fnd_diam(int v){
    mx = -1, mxver = 0;
    dfs2(v, 0, 0);
    mx = -1;
    dfs2(mxver, 0, 0);
    return mx;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> nxt[i] >> len[i];
        g[i].push_back(i);
        g[nxt[i]].push_back(i);
    }
    for (int i = 1; i <= n; i++){
        if (used[i])
            continue;

        fnd_cycle(i, 0);


        vector <int> cycle;
        vector <ll> lens;
        cycle.push_back(cStrt);
        lens.push_back(0);
        lens.push_back(len[cId]);
        block[cId] = 1;
        for (int v = cEnd; v != cStrt; v = pr[v]){
            cId = pr2[v];
            cycle.push_back(v);
            lens.push_back(len[cId]);
            block[cId] = 1;
        }
        for (int j = 1; j < lens.size(); j++){
            lens[j] += lens[j-1];
        }

        ll curans = 0;

        ll mx1 = -1e18, mx2 = -1e18;


        for (int j = 0; j < cycle.size(); j++){
            int v = cycle[j];
            used[v] = 1;

            ll curmx = 0;
            for (int j = 0; j < g[v].size(); j++){
                int id = g[v][j];
                int to = getTo(v, id);
                if (block[id])
                    continue;
                curmx = max(curmx, dfs(to, v)+len[id]);
            }

            curans = max(curans, curmx);
            curans = max(curans, fnd_diam(v));

            if (j == 0){

                mx1 = max(mx1, curmx);
                mx2 = max(mx2, curmx);

            } else {

                curans = max(curans, curmx+lens[j] + mx1 );
                curans = max(curans, curmx+lens.back()-lens[j] + mx2 );

                mx1 = max(mx1, curmx-lens[j]);
                mx2 = max(mx2, curmx+lens[j]);

            }

        }

        ans += curans;

    }
    cout << ans;


}

컴파일 시 표준 에러 (stderr) 메시지

islands.cpp: In function 'int fnd_cycle(int, int)':
islands.cpp:29:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
islands.cpp: In function 'll dfs(int, int)':
islands.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
islands.cpp: In function 'void dfs2(int, int, ll)':
islands.cpp:74:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++){
                     ~~^~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:118:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < lens.size(); j++){
                         ~~^~~~~~~~~~~~~
islands.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < cycle.size(); j++){
                         ~~^~~~~~~~~~~~~~
islands.cpp:132:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[v].size(); j++){
                             ~~^~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10