oj.uz

Submission #931096

# Submission time Handle Problem Language Result Execution time Memory
931096 2024-02-21T08:29:51 Z Art_ogo Dreaming (IOI13_dreaming) C++17
18 / 100
 50 ms 21332 KB 
#include <bits/stdc++.h>
#include "dreaming.h"

#define ve vector 
#define all(x) x.begin(), x.end()
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5+10;

ve<pii> g[MAXN];
bool vis[MAXN];
int dst[MAXN];
int mxdst[MAXN];

void calcdst(int v){
    vis[v] = 1;
    mxdst[v] = dst[v];
    for(auto to : g[v])
        if(!vis[to.fi]){
            dst[to.fi] = dst[v] + to.se;
            calcdst(to.fi);
            mxdst[v] = max(mxdst[v], mxdst[to.fi]);
        }
}

int dfs(int v, int p, int curmx, int cur){
    ve<int> dsts = {curmx};
    for(auto& to : g[v])
        if(to.fi != p)
            dsts.push_back(mxdst[to.fi] - cur);
    sort(all(dsts), greater<int>());
    int res = dsts[0];
    multiset<int, greater<int> > cdst;
    for(auto i : dsts)
        cdst.insert(i);
    for(auto& to : g[v])
        if(to.fi != p){
            cdst.erase(cdst.find(mxdst[to.fi] - cur));
            res = min(res, dfs(to.fi, v, *cdst.begin() + to.se, cur + to.se));
            cdst.insert(mxdst[to.fi] - cur);
        }
    return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++){
        int u = A[i], v = B[i], w = T[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    ve<int> v;
    for(int i = 0; i < N; i++)
        if(!vis[i]){
            calcdst(i);
            v.push_back(dfs(i, i, 0, 0));
        }
    sort(all(v), greater<int>());
    if(v.size() == 1)
        return v[0];
    else if(v.size() == 2)
        return v[0] + v[1] + L;
    else 
        return max(v[0] + v[1] + L, v[1] + v[2] + 2*L);
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 21332 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 50 ms 21332 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 20 ms 7124 KB Output is correct
2 Correct 19 ms 7132 KB Output is correct
3 Correct 19 ms 7004 KB Output is correct
4 Correct 18 ms 7132 KB Output is correct
5 Correct 19 ms 7132 KB Output is correct
6 Correct 20 ms 7468 KB Output is correct
7 Correct 19 ms 7132 KB Output is correct
8 Correct 22 ms 7392 KB Output is correct
9 Correct 18 ms 7004 KB Output is correct
10 Correct 20 ms 7384 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 7 ms 5336 KB Output is correct
13 Correct 7 ms 5336 KB Output is correct
14 Correct 7 ms 5336 KB Output is correct
15 Correct 7 ms 5336 KB Output is correct
16 Correct 7 ms 5336 KB Output is correct
17 Correct 7 ms 5080 KB Output is correct
18 Correct 8 ms 5336 KB Output is correct
19 Correct 7 ms 5332 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 4700 KB Output is correct
23 Correct 7 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 50 ms 21332 KB Output isn't correct
2 Halted 0 ms 0 KB -