oj.uz

Submission #114473

# Submission time Handle Problem Language Result Execution time Memory
114473 2019-06-01T12:39:20 Z popovicirobert Islands (IOI08_islands) C++14
80 / 100
 632 ms 131072 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const ll INF = 1e18;

struct Edge {
    int nod, cst;
    int id;
};

vector < vector <Edge> > g;
vector <int> vis;
vector < pair <int, int> > cyc;

vector < pair <int, int> > stk;
vector <int> nodes;

static void get_cyc(int nod, int id) {
    nodes.push_back(nod);
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(vis[it.nod] == 0) {
            stk.push_back({nod, it.cst});
            get_cyc(it.nod, it.id);
            stk.pop_back();
        }
        else if(vis[it.nod] == 1 && it.id != id) {
            int i = (int) stk.size() - 1;
            while(i >= 0 && stk[i].first != it.nod) {
                cyc.push_back(stk[i]);
                i--;
            }
            cyc.push_back(stk[i]);
            reverse(cyc.begin(), cyc.end());
            cyc.push_back({nod, it.cst});
        }
    }
    vis[nod] = 2;
}

vector <ll> dp1, dp2;

static void dfs(int nod, ll &ans)  {
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(vis[it.nod] == 0) {
            dfs(it.nod, ans);
            ll cur = dp1[it.nod] + it.cst;
            if(dp1[nod] <= cur) {
                dp2[nod] = dp1[nod];
                dp1[nod] = cur;
            }
            else if(dp2[nod] <= cur) {
                dp2[nod] = cur;
            }
        }
    }
    ans = max(ans, dp1[nod] + dp2[nod]);
}


inline ll solve(int nod) {

    cyc.clear(), nodes.clear();
    get_cyc(nod, 0);

    for(auto it : nodes) {
        vis[it] = 0;
    }
    ll sum = 0;
    for(auto it : cyc) {
        vis[it.first] = 1;
        sum += it.second;
    }

    ll cur = 0, mx1 = -INF, mx2 = -INF, ans = 0;
    for(auto it : cyc) {
        dfs(it.first, ans);
        if(it.first != cyc[0].first) {
            ans = max(ans, max(mx1 + dp1[it.first] + cur, mx2 + dp1[it.first] - cur));
        }
        mx1 = max(mx1, dp1[it.first] - cur);
        mx2 = max(mx2, dp1[it.first] + cur + sum);
        cur += it.second;
    }

    return ans;

}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    g.resize(n + 1);
    for(i = 1; i <= n; i++) {
        int nod, cst;
        cin >> nod >> cst;
        g[i].push_back({nod, cst, i});
        g[nod].push_back({i, cst, i});
    }

    vis.resize(n + 1);
    dp1.resize(n + 1), dp2.resize(n + 1);

    ll ans = 0;
    for(i = 1; i <= n; i++) {
        if(vis[i] == 0) {
            ans += solve(i);
        }
    }

    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1920 KB Output is correct
2 Correct 24 ms 5500 KB Output is correct
3 Correct 15 ms 2304 KB Output is correct
4 Correct 8 ms 1408 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7340 KB Output is correct
2 Correct 41 ms 11072 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 20656 KB Output is correct
2 Correct 103 ms 26656 KB Output is correct
3 Correct 140 ms 41112 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 35392 KB Output is correct
2 Correct 220 ms 69392 KB Output is correct
3 Correct 238 ms 75488 KB Output is correct
4 Correct 330 ms 102764 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 94480 KB Output is correct
2 Runtime error 632 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 392 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -