oj.uz

Submission #875414

# Submission time Handle Problem Language Result Execution time Memory
875414 2023-11-19T15:24:10 Z AverageAmogusEnjoyer Dreaming (IOI13_dreaming) C++17
18 / 100
 45 ms 19420 KB 
#include "bits/stdc++.h"
#include "dreaming.h"
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,1:0; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,1:0; }
const int N=1e5;
vector<pair<int,int>> adj[N];
int dp[N],dp2[N];
bool done[N];
vector<int> cc;
void getCC(int u,int e) {
    cc.push_back(u);
    for (auto &[v,len]: adj[u]) if (v!=e) {
        getCC(v,u);
    }
}
void dfs(int u,int e) {
    for (auto &[v,len]: adj[u]) if (v!=e) {
        dfs(v,u);
        cmax(dp[u],dp[v]+len);
    }
}
void dfs2(int u,int e) {
    multiset<int> lengths;
    lengths.insert(dp2[u]);
    for (auto &[v,len]: adj[u]) if (v!=e) {
        lengths.insert(dp[v]+len);
    }
    for (auto &[v,len]: adj[u]) if (v!=e) {
        lengths.erase(lengths.find(dp[v]+len));
        assert(!lengths.empty());
        dp2[v]=*lengths.rbegin()+len;
        dfs2(v,u);
        lengths.insert(dp[v]+len);
    }
}
int travelTime(int n, int m, int k, int u[], int v[], int len[]) {
    for (int i=0;i<m;i++) {
        adj[u[i]].emplace_back(v[i],len[i]);
        adj[v[i]].emplace_back(u[i],len[i]);
    }
    vector<int> diams;
    const int inf = 1e9;
    for (int i=0;i<n;i++) {
        if (!done[i]) {
            cc.clear();
            getCC(i,-1);
            for (int &j: cc) {
                assert(!done[j]);
                done[j]=true;
            }
            dfs(i,-1);
            dfs2(i,-1);
            int rs=inf;
            for (int &j: cc) {
                cmin(rs,max(dp[j],dp2[j]));
            }
            diams.push_back(rs);
            // dp[u] = max dist in subtree of u,
            // dp2[u] = max dist in everything except subtree of u
        }
    }
    sort(diams.begin(),diams.end());
    n = int(diams.size());
    if (diams.size()==1) {
        return diams[0];
    } else if (diams.size()==2) {
        return diams[0]+diams[1]+k;
    } else {
        return max(diams[n-1]+diams[n-2]+k,diams[n-2]+diams[n-3]+2*k);
    }
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 7516 KB Output is correct
2 Correct 16 ms 7516 KB Output is correct
3 Correct 16 ms 7500 KB Output is correct
4 Correct 16 ms 7512 KB Output is correct
5 Correct 16 ms 7512 KB Output is correct
6 Correct 18 ms 7904 KB Output is correct
7 Correct 17 ms 7648 KB Output is correct
8 Correct 16 ms 7392 KB Output is correct
9 Correct 16 ms 7384 KB Output is correct
10 Correct 17 ms 7640 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 6 ms 5132 KB Output is correct
13 Correct 6 ms 5332 KB Output is correct
14 Correct 6 ms 5332 KB Output is correct
15 Correct 6 ms 5336 KB Output is correct
16 Correct 6 ms 5336 KB Output is correct
17 Correct 5 ms 5080 KB Output is correct
18 Correct 6 ms 5336 KB Output is correct
19 Correct 5 ms 5336 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4672 KB Output is correct
23 Correct 6 ms 5336 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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