oj.uz

Submission #304592

# Submission time Handle Problem Language Result Execution time Memory
304592 2020-09-21T14:49:27 Z rocks03 Islands (IOI08_islands) C++14
40 / 100
 2000 ms 122504 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pld pair<long double, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define ff first
#define ss second
#define SZ(x) ((int)(x).size())
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e6+100;
int N;
vector<pii> adj[MAXN];

void read(){
    cin >> N;
    for(int i = 0; i < N; i++){
        int u, w;
        cin >> u >> w;
        --u;
        adj[i].pb({u, w});
        adj[u].pb({i, w});
    }
}

bool vis[MAXN], vis2[MAXN];
vector<int> componente;

void dfs(int v){
    vis[v] = true;
    componente.pb(v);
    for(auto u : adj[v]){
        if(!vis[u.ff]){
            dfs(u.ff);
        }
    }
}

ll dfs2(int v){
    ll ans = 0;
    vis2[v] = true;
    for(auto u : adj[v]){
        if(!vis2[u.ff]){
            ans = max(ans, dfs2(u.ff) + u.ss);
        }
    }
    vis2[v] = false;
    return ans;
}

void solve(){
    read();
    ll ans = 0;
    for(int i = 0; i < N; i++){
        if(!vis[i]){
            dfs(i);
            ll res = 0;
            for(auto v : componente){
                res = max(res, dfs2(v));
            }
            ans += res;
            componente.clear();
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 20 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23808 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 15 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 15 ms 23808 KB Output is correct
10 Correct 15 ms 23808 KB Output is correct
11 Correct 16 ms 23808 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 23984 KB Output is correct
2 Correct 16 ms 23936 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24000 KB Output is correct
2 Correct 747 ms 24312 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 24740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 27776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 35952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 44408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 88528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 122504 KB Time limit exceeded
2 Halted 0 ms 0 KB -