oj.uz

Submission #1038829

# Submission time Handle Problem Language Result Execution time Memory
1038829 2024-07-30T08:05:49 Z inkvizytor Dreaming (IOI13_dreaming) C++17
18 / 100
 27 ms 11856 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> spoj;
vector<vector<pair<int, int>>> g;
vector<int> maxodl1;
vector<int> maxodl2;
vector<int> sr;
vector<int> srdl;
vector<bool> odw;
vector<bool> odws;

void dfs (int v) {
    for (auto u : g[v]) {
        if (!spoj[u.first]) {
            spoj[u.first] = spoj[v];
            dfs(u.first);
            if (maxodl1[v] < maxodl1[u.first]+u.second) {
                maxodl2[v] = maxodl1[v];
                maxodl1[v] = maxodl1[u.first]+u.second;
            }
            else {
                maxodl2[v] = max(maxodl2[v], maxodl1[u.first]+u.second);
            }
        }
    }
}

int odlg = 0;

void zsr (int v) {
    int x = v;
    while (true) {
        sr[spoj[x]] = x;
        srdl[spoj[x]] = maxodl1[x];
        bool b = 0;
        for (auto u : g[x]) {
            if (odw[u.first]) {
                continue;
            }
            odw[u.first] = 1;
            if (maxodl1[x] == maxodl1[u.first]+u.second && max(maxodl2[x], odlg)+u.second < srdl[spoj[x]]) {
                odlg = max(maxodl2[x], odlg)+u.second;
                srdl[spoj[x]] = max(maxodl1[x], odlg);
                x = u.first;
                b = 1;
                break;
            }
        }
        if (!b) {
            break;
        } 
    }
}


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    g.resize(N);
    for (int i = 0; i < M; i++) {
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    spoj.resize(N, 0);
    maxodl1.resize(N, 0);
    maxodl2.resize(N, 0);
    int nspoj = 1;
    for (int i = 0; i < N; i++) {
        if (!spoj[i]) {
            spoj[i] = nspoj;
            nspoj++;
            dfs(i);
        }
    }
    sr.resize(nspoj, 0);
    srdl.resize(nspoj, 0);
    odw.resize(N, 0);
    odws.resize(nspoj, 0);
    for (int i = 0; i < N; i++) {
        if (!odws[spoj[i]]) {
            odlg = 0;
            odw[i] = 1;
            odws[spoj[i]] = 1;
            zsr(i);
        }
    }
    int max1 = 0, max2 = 0, max3 = 0;
    for (int i : srdl) {
        if (i > max1) {
            max3 = max2;
            max2 = max1;
            max1 = i;
        }
        else if (i > max2) {
            max3 = max2;
            max2 = i;
        }
        else {
            max3 = max(max3, i);
        }
    }
    if (M == N-1) {
        return max1;
    }
    else if (M == N-2) {
        return max1+max2+L;
    }
    return max(max1+max2+L,max2+max3+2*L);
}

Subtask #1
0 / 14.0

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

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 Incorrect 27 ms 11856 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 12 ms 6992 KB Output is correct
2 Correct 12 ms 7044 KB Output is correct
3 Correct 15 ms 7000 KB Output is correct
4 Correct 17 ms 7004 KB Output is correct
5 Correct 12 ms 7004 KB Output is correct
6 Correct 13 ms 7256 KB Output is correct
7 Correct 13 ms 7260 KB Output is correct
8 Correct 12 ms 6900 KB Output is correct
9 Correct 12 ms 6744 KB Output is correct
10 Correct 13 ms 7260 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 3 ms 4700 KB Output is correct
15 Correct 3 ms 4700 KB Output is correct
16 Correct 3 ms 4700 KB Output is correct
17 Correct 3 ms 4700 KB Output is correct
18 Correct 3 ms 4700 KB Output is correct
19 Correct 3 ms 4700 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 3 ms 4700 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 Incorrect 27 ms 11856 KB Output isn't correct
2 Halted 0 ms 0 KB -