oj.uz

Submission #217471

# Submission time Handle Problem Language Result Execution time Memory
217471 2020-03-29T20:12:27 Z tatyam Islands (IOI08_islands) C++17
21 / 100
 469 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 0x1fffffffffffffff;
#define name3(a,b,c,d,...) d
#define rep1(a) for(ll i = 0; i < a; i++)
#define rep3(i,a,b) for(ll i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(a) for(ll i = a; i--; )
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }


vector<bool> used;
vector<vector<pll>> g;
vector<ll> in;
ll ans = 0;
void solve(ll start){
    if(used[start]) return;
    vector<ll> list = {start};
    used[start] = 1;
    rep(list.size()){
        ll at = list[i];
        each(i, g[at]) if(!used[i.first]){
            used[i.first] = 1;
            list.push_back(i.first);
        }
    }
    ll mx = 0;
    ll dex = -1;
    unordered_map<ll, ll> dp;
    each(i, list) if(g[i].size() == 1){
        ll cnt = 0;
        ll at = i;
        while(g[at].size() < 3){
            cnt += g[at][0].second;
            at = g[at][0].first;
        }
        chmax(dp[at], cnt);
        if(chmax(mx, cnt)) dex = at;
    }
    if(!mx){
        ll min = INF;
        each(at, list){
            ans += g[at][0].second;
            chmin(min, g[at][0].second);
        }
        ans -= min;
        return;
    }
    vector<ll> circle, dist;
    ll at = dex;
    do{
        circle.push_back(at);
        dist.push_back(g[at][0].second);
        at = g[at][0].first;
    } while(at != dex);
    circle.push_back(at);
    dp[dex] = 0;
    auto dp2 = dp;
    rep(i, 1, dist.size()) chmax(dp[circle[i + 1]], dp[circle[i]] + dist[i]);
    rrep(dist.size() - 1) chmax(dp2[circle[i]], dp2[circle[i + 1]] + dist[i]);
    ans += mx + max(dp[dex], dp2[dex]);
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    used.resize(n);
    g.resize(n);
    in.resize(n);
    rep(n){
        ll a, b;
        cin >> a >> b;
        a--;
        g[i].emplace_back(a, b);
    }
    rep(n) g[g[i][0].first].emplace_back(i, g[i][0].second);
    rep(n) solve(i);
    cout << ans << endl;
}

Compilation message

islands.cpp: In function 'void solve(ll)':
islands.cpp:7:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep1(a) for(ll i = 0; i < a; i++)
                                 ^
islands.cpp:6:28: note: in expansion of macro 'rep1'
 #define name3(a,b,c,d,...) d
                            ^
islands.cpp:9:18: note: in expansion of macro 'name3'
 #define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
                  ^~~~~
islands.cpp:25:5: note: in expansion of macro 'rep'
     rep(list.size()){
     ^~~
islands.cpp:8:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep3(i,a,b) for(ll i = a; i < b; i++)
                                     ^
islands.cpp:6:28: note: in expansion of macro 'rep3'
 #define name3(a,b,c,d,...) d
                            ^
islands.cpp:9:18: note: in expansion of macro 'name3'
 #define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
                  ^~~~~
islands.cpp:64:5: note: in expansion of macro 'rep'
     rep(i, 1, dist.size()) chmax(dp[circle[i + 1]], dp[circle[i]] + dist[i]);
     ^~~

Subtask #1
21.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Runtime error 212 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Incorrect 4 ms 384 KB Output isn't correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Runtime error 198 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 5 ms 384 KB Output is correct
10 Incorrect 5 ms 384 KB Output isn't correct
11 Correct 5 ms 256 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 7540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 25172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 404 ms 110460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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