oj.uz

답안 #114503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114503 2019-06-01T13:28:47 Z popovicirobert Islands (IOI08_islands) C++14
80 / 100
 2000 ms 113736 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 < 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;
}

Compilation message

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.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 384 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

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

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 5 ms 768 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1792 KB Output is correct
2 Correct 29 ms 3968 KB Output is correct
3 Correct 15 ms 2432 KB Output is correct
4 Correct 10 ms 1356 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 5500 KB Output is correct
2 Correct 46 ms 9592 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 19308 KB Output is correct
2 Correct 115 ms 20356 KB Output is correct
3 Correct 142 ms 27308 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 35552 KB Output is correct
2 Correct 253 ms 52044 KB Output is correct
3 Correct 262 ms 51840 KB Output is correct
4 Correct 343 ms 68008 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 106560 KB Output is correct
2 Correct 1468 ms 103600 KB Output is correct
3 Correct 373 ms 82852 KB Output is correct
4 Correct 520 ms 111208 KB Output is correct
5 Correct 528 ms 113736 KB Output is correct
6 Execution timed out 2048 ms 108772 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 437 ms 88760 KB Output is correct
2 Correct 424 ms 88676 KB Output is correct
3 Correct 462 ms 90976 KB Output is correct
4 Correct 528 ms 78716 KB Output is correct
5 Correct 497 ms 101992 KB Output is correct
6 Correct 621 ms 90092 KB Output is correct
7 Execution timed out 2092 ms 108052 KB Time limit exceeded