제출 #114503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114503		popovicirobert	Islands (IOI08_islands)	C++14	80 / 100	2092 ms	113736 KiB

islands

#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 < pair <int, int> > cyc;
vector <int> nodes, vis, deg;

void get_cyc(int nod) {
    queue <int> Q;
    Q.push(nod), vis[nod] = 1;

    while(Q.size()) {
        nod = Q.front(), nodes.push_back(nod);
        Q.pop();

        for(auto it : g[nod]) {
            if(vis[it.nod] == 0) {
                vis[it.nod] = 1;
                Q.push(it.nod);
            }
        }
    }

    for(auto it : nodes) {
        vis[it] = 0;
        if(deg[it] == 1) {
            Q.push(it);
            vis[it] = 1;
        }
    }

    while(Q.size()) {
        nod = Q.front();
        Q.pop();

        for(auto it : g[nod]) {
            deg[it.nod]--;
            if(deg[it.nod] == 1) {
                Q.push(it.nod);
                vis[it.nod] = 1;
            }
        }
    }

    for(auto it : nodes) {
        if(vis[it] == 0) {
            nod = it;
            break;
        }
    }

    int root = nod, flag = 1, id = 0;
    vis[nod] = 1;

    while(flag) {
        for(auto it : g[nod]) {
            if(vis[it.nod] == 0) {
                vis[it.nod] = 1;
                cyc.push_back({nod, it.cst});
                id = it.id, nod = it.nod;
                break;
            }
            else if(it.nod == root && it.id != id) {
                cyc.push_back({nod, it.cst});
                flag = 0;
            }
        }
    }
}

vector <ll> dp1, dp2;

void dfs(int nod, ll &ans)  {
    vector <int> Q;
    int sz = 0;
    Q.push_back(nod);
    vis[nod] = 1;

    while(sz < Q.size()) {
        nod = Q[sz++];
        for(auto it : g[nod]) {
            if(vis[it.nod] == 0) {
                vis[it.nod] = 2;
                Q.push_back(it.nod);
            }
        }
    }

    reverse(Q.begin(), Q.end());
    for(auto nod : Q) {
        dp1[nod] = dp2[nod] = 0;
        for(auto it : g[nod]) {
            if(vis[it.nod] == 1) {
                continue;
            }
            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);

    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), deg.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});
        deg[i]++, deg[nod]++;
    }

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

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

    cout << ans;

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

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

islands.cpp: In function 'void dfs(int, long long int&)':
islands.cpp:92:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(sz < Q.size()) {
           ~~~^~~~~~~~~~

• 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