Submission #410525

#	Time	Username	Problem	Language	Result	Execution time	Memory
410525		AugustinasJucas	Islands (IOI08_islands)	C++14	80 / 100	757 ms	131076 KiB

islands

            #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;
             	long long opcija;
                for (auto x : grafas[v]) {
                    if (x.first == came) {
                        continue;
                    }
             
                    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};
        	long long sm1, sm2, st, atsak, mx1, mx2, sum, m, did1, did2;
            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});
                }
             
                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;
                        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;*/
                    sum = 0;
             
                    for (auto x : cNodes1) {
                        sum += wh[x];
                    }
             
                    m = cNodes1.size();
                    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]);
             
                        did1 = (*pirmas.rbegin()) + cycVal[cNodes1[j]] - pref[j];
                        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 / 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: 0 / 10
• Subtask 9: 0 / 10