oj.uz

답안 #114674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114674 2019-06-02T09:29:23 Z zubec Islands (IOI08_islands) C++14
44 / 100
 470 ms 131072 KB 
#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 <pair<int, int> > g[N], gg[N];

bool used[N], inCycle[N];

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

int cId;

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

    for (int i = 0; i < gg[v].size(); i++){
        int to = gg[v][i].first, id = gg[v][i].second;
        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 to = g[v][i].first;
        if (to == p)
            continue;
        curmx = max(curmx, dfs(to, v)+g[v][i].second);
    }
    return curmx;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++){
        int to;
        cin >> to >> len[i];
        nxt[i] = to;
        g[i].push_back({to, len[i]});
        gg[i].push_back({to, i});
        g[to].push_back({i, len[i]});
        gg[to].push_back({i, 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]);
        for (int v = cEnd; v != cStrt; v = pr[v]){
            cId = pr2[cId];
            cycle.push_back(v);
            lens.push_back(len[cId]);
        }
        for (int j = 0; j < cycle.size(); j++){
            inCycle[cycle[j]] = 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 to = g[v][j].first;
                if (inCycle[to])
                    continue;
                curmx = max(curmx, dfs(to, v)+g[v][j].second);
            }

            curans = max(curans, curmx);

            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;


}

Compilation message

islands.cpp: In function 'int fnd_cycle(int, int)':
islands.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < gg[v].size(); i++){
                     ~~^~~~~~~~~~~~~~
islands.cpp: In function 'll dfs(int, int)':
islands.cpp:52: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:90:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < cycle.size(); j++){
                         ~~^~~~~~~~~~~~~~
islands.cpp:93:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < lens.size(); j++){
                         ~~^~~~~~~~~~~~~
islands.cpp:101:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < cycle.size(); j++){
                         ~~^~~~~~~~~~~~~~
islands.cpp:106:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[v].size(); j++){
                             ~~^~~~~~~~~~~~~

Subtask #1
21.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 47352 KB Output is correct
2 Incorrect 42 ms 47360 KB Output isn't correct
3 Correct 41 ms 47480 KB Output is correct
4 Correct 41 ms 47360 KB Output is correct
5 Correct 43 ms 47352 KB Output is correct
6 Incorrect 44 ms 47480 KB Output isn't correct
7 Correct 41 ms 47360 KB Output is correct
8 Incorrect 42 ms 47352 KB Output isn't correct
9 Correct 41 ms 47352 KB Output is correct
10 Incorrect 43 ms 47356 KB Output isn't correct
11 Correct 44 ms 47428 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 53560 KB Output is correct
2 Correct 93 ms 57848 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 67800 KB Output is correct
2 Correct 172 ms 71252 KB Output is correct
3 Correct 203 ms 81396 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 85376 KB Output is correct
2 Incorrect 324 ms 108908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 385 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 470 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -