oj.uz

Submission #1004695

# Submission time Handle Problem Language Result Execution time Memory
1004695 2024-06-21T12:46:11 Z Gray Dreaming (IOI13_dreaming) C++17
32 / 100
 49 ms 21080 KB 
#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <vector>

#define ll long long
#define ff first
#define ss second
#define ln "\n"

using namespace std;
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
vector<vector<ll>> dp;
vector<ll> stmp;
vector<bool> vis;
ll n, m, l;
void dfs(ll u, ll p){
    vis[u]=1;
    if (A[u].size()==1 and u!=p){
        dp[u] = {0};
    }
    for (auto i:A[u]){
        ll v = e[i].ss.ff^e[i].ss.ss^u;
        if (v==p) continue;
        dfs(v, u);
        for (auto ch:dp[v]){
            dp[u].push_back(ch+e[i].ff);
        }
    }
    sort(dp[u].rbegin(), dp[u].rend());
    while (dp[u].size()>2) dp[u].pop_back();
}
void dfs2(ll u, ll p, ll &diam, ll &big, ll pass){
    // cout << u << endl;
    dp[u].push_back(pass);
    sort(dp[u].rbegin(), dp[u].rend());
    while (dp[u].size()>2) dp[u].pop_back();
    for (auto i:A[u]){
        ll v = e[i].ss.ff^e[i].ss.ss^u;
        if (v==p) continue;
        if (dp[u][0]==dp[v][0]+e[i].ff){
            dfs2(v, u, diam, big, dp[u][1]+e[i].ff);
        }else{
            dfs2(v, u, diam, big, dp[u][0]+e[i].ff);
        }
    }
    // cout << u << " <> " << dp[u][0] << ln;
    if (dp[u].size()==1){
        diam=max(diam, dp[u][0]);
        big=0;
        return;
    }
    diam=max(diam, dp[u][0]+dp[u][1]);
    big=min(big, dp[u][0]);
}
pair<ll, ll> fout(ll mem){
    dfs(mem, mem);
    ll diam=0, big=2e18;
    dfs2(mem, mem, diam, big, 0);
    // cout << mem << " -> " << diam << " " << big << endl;
    return {diam, big};
}
int travelTime(int N, int M, int L, int U[], int V[], int W[]) {
    n=N; m=M; l=L;
    // cout << N << " " << M << " " << L << ln;return 0;
    e.resize(m);
    A.resize(n);
    dp.resize(n);
    vis.resize(n);
    // return 0;
    for (ll i=0; i<m; i++){
        A[U[i]].push_back(i);
        A[V[i]].push_back(i);
        e[i] = {W[i], {U[i], V[i]}};
    }
    ll ans=0;
    vector<ll> bigs;
    for (ll i=0; i<n; i++){
        // cout << i << ":";
        if (!vis[i]){
            // cout << i << endl;
            auto ret = fout(i);
            ans=max(ans, ret.ff);
            bigs.push_back(ret.ss);
        }
    }
    sort(bigs.rbegin(), bigs.rend());
    ans=max(ans, bigs[0]);
    if (bigs.size()>1){
        ans=max(ans, bigs[0]+bigs[1]+l);
    }
    if (bigs.size()>2){
        ans=max(ans, bigs[1]+bigs[2]+2*l);
    }
    return ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 21080 KB Output is correct
2 Correct 43 ms 20564 KB Output is correct
3 Correct 28 ms 16464 KB Output is correct
4 Correct 6 ms 3420 KB Output is correct
5 Correct 5 ms 2396 KB Output is correct
6 Correct 11 ms 4956 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 25 ms 9132 KB Output is correct
9 Correct 29 ms 13140 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 44 ms 15700 KB Output is correct
12 Correct 49 ms 18256 KB Output is correct
13 Correct 1 ms 600 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 21080 KB Output is correct
2 Correct 43 ms 20564 KB Output is correct
3 Correct 28 ms 16464 KB Output is correct
4 Correct 6 ms 3420 KB Output is correct
5 Correct 5 ms 2396 KB Output is correct
6 Correct 11 ms 4956 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 25 ms 9132 KB Output is correct
9 Correct 29 ms 13140 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 44 ms 15700 KB Output is correct
12 Correct 49 ms 18256 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11720 KB Output is correct
2 Correct 24 ms 11720 KB Output is correct
3 Correct 26 ms 11724 KB Output is correct
4 Correct 26 ms 11720 KB Output is correct
5 Correct 22 ms 11500 KB Output is correct
6 Correct 23 ms 12916 KB Output is correct
7 Correct 22 ms 12236 KB Output is correct
8 Correct 21 ms 11472 KB Output is correct
9 Correct 21 ms 11476 KB Output is correct
10 Correct 30 ms 11988 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 13 ms 9008 KB Output is correct
13 Correct 9 ms 8908 KB Output is correct
14 Correct 9 ms 9008 KB Output is correct
15 Correct 9 ms 8912 KB Output is correct
16 Correct 9 ms 8912 KB Output is correct
17 Correct 8 ms 8876 KB Output is correct
18 Correct 10 ms 8912 KB Output is correct
19 Correct 9 ms 8912 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 9 ms 9020 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 21080 KB Output is correct
2 Correct 43 ms 20564 KB Output is correct
3 Correct 28 ms 16464 KB Output is correct
4 Correct 6 ms 3420 KB Output is correct
5 Correct 5 ms 2396 KB Output is correct
6 Correct 11 ms 4956 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 25 ms 9132 KB Output is correct
9 Correct 29 ms 13140 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 44 ms 15700 KB Output is correct
12 Correct 49 ms 18256 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -