oj.uz

Submission #410518

# Submission time Handle Problem Language Result Execution time Memory
410518 2021-05-22T21:07:44 Z AugustinasJucas Islands (IOI08_islands) C++14
80 / 100
 748 ms 131076 KB 
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int dydis = 1e6 + 100;
const long long inf = 1000000000000000000;
int n;
int ind;
long long opcija, pries, pgl, delta;
vector<pair<int, int> > grafas[dydis];
int gr[dydis] = {0};
int wh[dydis] = {0};
bool vis[dydis] = {0};
bool visited[dydis] = {0};
bool inCycle[dydis] = {0};
long long cycVal[dydis] = {0};
long long pref[dydis], suf[dydis];
multiset<long long> pirmas, antras;
void dfs(int v, int prim) {
    queue<int> q;
    q.push(v);

    while (!q.empty()) {
        v = q.front();
        q.pop();

        if (visited[v]) {
            continue;
        }

        visited[v] = 1;

        for (auto x : grafas[v]) {
            if (visited[x.first]) {
                continue;
            }

            q.push(x.first);
        }
    }
}

vector<int> cNodes, cNodes1;
bool fd = 0;
void findCycle(int v) {
    if (fd) {
        return;
    }

    if (vis[v]) {
        cNodes.push_back(v);
        fd = 1;
        return;
    }

    if (!fd) {
        cNodes.push_back(v);
    }

    vis[v] = 1;
    findCycle(gr[v]);

    if (!fd) {
        cNodes.pop_back();
    }
}
long long otherVal = 0;
long long dfs1(int v, int came) {
    long long ret = 0;
    long long mx1 = 0;
    long long mx2 = 0;

    for (auto x : grafas[v]) {
        if (x.first == came) {
            continue;
        }

        long long opcija = dfs1(x.first, v) + x.second;

        if (opcija > mx1) {
            mx2 = mx1;
            mx1 = opcija;
        }
        else if (opcija > mx2) {
            mx2 = opcija;
        }

        ret = max(ret, opcija);
    }

    otherVal = max(otherVal, mx1 + mx2);
    return ret;
}
void removeVal(multiset<long long> &st, long long val) {
    auto itr = st.find(val);

    if (itr != st.end()) {
        st.erase(itr);
    }

}
bool yraKairej[dydis] = {0};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        gr[i] = a;
        wh[i] = b;
        grafas[a].push_back({i, b});
        grafas[i].push_back({a, b});
    }

    long long atsak = 0;

    for (int i = 0; i < n; i++) {
        if (visited[i]) {
            continue;
        }

        dfs(i, i);
        cNodes1.clear();
        cNodes.clear();
        fd = 0;
        findCycle(i);
        bool can = 0;

        for (auto x : cNodes) {
            if (x == cNodes.back()) {
                can = 1;
            }

            if (can) {
                cNodes1.push_back(x);
            }
        }

        cNodes1.pop_back();

        for (auto x : cNodes1) {
            inCycle[x] = 1;
        }

        otherVal = 0;

        for (auto x : cNodes1) {
            cycVal[x] = 0;
            long long mx1 = 0, mx2 = 0;

            for (auto y : grafas[x])
                if (!inCycle[y.first]) {
                    opcija = dfs1(y.first, x) + y.second;
                    cycVal[x] = max(cycVal[x], opcija);

                    if (opcija > mx1) {
                        mx2 = mx1;
                        mx1 = opcija;
                    }
                    else if (opcija > mx2) {
                        mx2 = opcija;
                    }

                    otherVal = max(otherVal, mx1 + mx2);
                }
        }/*

        cout << i <<  " cycle = ";
        for(auto x : cNodes1){
            cout << "{" << x << ", " << cycVal[x] << "} ";
        }
        cout << endl << endl;*/
        long long sum = 0;

        for (auto x : cNodes1) {
            sum += wh[x];
        }

        int m = cNodes1.size();
        long long st = 0;

        pref[0] = 0;
        suf[m - 1] = 0;

        for (int j = 1; j < m; j++) {
            pref[j] = pref[j - 1] + wh[cNodes1[j - 1]];
        }

        for (int j = m - 2; j > -1; j--) {
            suf[j] = suf[j + 1] + wh[cNodes1[j]];
        }

        // ats1 = mas[i] + mas[j] + pref[j] - pref[i]
        // ats1 = (mas[i] - pref[i]) + (mas[j]+pref[j])
        //
        // ats2 = (pref[i] + mas[i] + x) + suf[j] + mas[j]


        for (int j = 0; j < m; j++) {
            pirmas.insert(cycVal[cNodes1[j]] + pref[j]);
            antras.insert(cycVal[cNodes1[j]] + suf[j]);
        }

        for (int j = 0; j < m - 1; j++) {
            removeVal(pirmas, cycVal[cNodes1[j]] + pref[j]);
            removeVal(antras, cycVal[cNodes1[j]] + suf[j]);

            long long did1 = (*pirmas.rbegin()) + cycVal[cNodes1[j]] - pref[j];
            long long did2 = (*antras.rbegin()) + pref[j] + wh[cNodes1[m - 1]] + cycVal[cNodes1[j]];
            st = max(st, max(did1, did2));
        }

        removeVal(pirmas, cycVal[cNodes1[m - 1]] + pref[m - 1]);
        removeVal(antras, cycVal[cNodes1[m - 1]] + suf[m - 1]);




        st = max(st, otherVal);
        atsak += st;
        //      cout << "DONE" << endl << endl << endl;
    }

    cout << atsak;
    return 0;
}
/*
 * 1) kai pridedu nauja node'a, jo reiksme bus atstumas iki pirmosios (pagal laikr. ) + cycVal[x]
 * 2) kai pasalinu nauja node'a, jo reiksme bus
 *
 */

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23756 KB Output is correct
2 Correct 16 ms 23832 KB Output is correct
3 Correct 17 ms 23868 KB Output is correct
4 Correct 16 ms 23756 KB Output is correct
5 Correct 16 ms 23864 KB Output is correct
6 Correct 16 ms 23784 KB Output is correct
7 Correct 16 ms 23820 KB Output is correct
8 Correct 16 ms 23756 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 16 ms 23756 KB Output is correct
11 Correct 16 ms 23884 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24012 KB Output is correct
2 Correct 17 ms 23956 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23932 KB Output is correct
2 Correct 21 ms 24344 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 25180 KB Output is correct
2 Correct 39 ms 28320 KB Output is correct
3 Correct 26 ms 25360 KB Output is correct
4 Correct 21 ms 24576 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 30064 KB Output is correct
2 Correct 74 ms 33096 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 40132 KB Output is correct
2 Correct 177 ms 47284 KB Output is correct
3 Correct 211 ms 62212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 52980 KB Output is correct
2 Correct 302 ms 85352 KB Output is correct
3 Correct 548 ms 94640 KB Output is correct
4 Correct 508 ms 122672 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 91420 KB Output is correct
2 Runtime error 748 ms 131076 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 131072 KB Output is correct
2 Correct 406 ms 105656 KB Output is correct
3 Runtime error 463 ms 131076 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -