oj.uz

Submission #402204

# Submission time Handle Problem Language Result Execution time Memory
402204 2021-05-11T12:26:14 Z Lobo Dreaming (IOI13_dreaming) C++17
32 / 100
 62 ms 13764 KB 
#include <bits/stdc++.h>
#include <dreaming.h>
 
using namespace std;

const long long INFll = 1e18;
const int INFii = 1e9;
const long long mod = (long long) 1e9 + 7;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back

#define maxn 110000
//LEMBRAR DE MUDAR

ii n, m, l, d1[maxn], d2[maxn], mark[maxn], pai[maxn], ans; 
vector<pair<ii,ii>> g[maxn];
vector<ii> raio;
pair<ii,ii> dia;
stack<ii> vis;


void dfs1(ii a, ii ant) {
    for(auto b : g[a]) {
        if(b.fr == ant) continue;

        d1[b.fr] = d1[a] + b.sc;
        dia = max(dia,mp(d1[b.fr],b.fr));
        dfs1(b.fr, a);
    }
}

void dfs2(ii a) {
    vis.push(a);
    mark[a] = 1;
    
    for(auto b : g[a]) {
        if(mark[b.fr]) continue;

        d2[b.fr] = d2[a] + b.sc;
        dia = max(dia,mp(d2[b.fr],b.fr));
        dfs2(b.fr);
    }
}


int travelTime(int N,int M,int L,int A[],int B[],int T[]) {
    n = N;
    m = M;
    l = L;

    for(ii i = 0; i < m; i++) {
        g[A[i]].pb(mp(B[i],T[i]));
        g[B[i]].pb(mp(A[i],T[i]));
    }

    ans = 0;
    for(ii i = 0; i < n; i++) {
        if(!mark[i]) {
            d1[i] = 0;
            dia = mp(0,i);
            dfs1(i,i);

            ii aux = dia.sc;
            d2[aux] = 0;
            dia = mp(0,aux);
            dfs2(aux);

            ii rai = INFii;
            ans = max(ans, dia.fr);

            while(!vis.empty()) {
                rai = min(rai, max(dia.fr - d2[vis.top()],d2[vis.top()]));
                vis.pop();
            }
            
            raio.pb(rai);
        }
    }

    sort(raio.begin(),raio.end());

    ii r1 = raio.back();
    raio.pop_back();

    ii r2 = -INFii;
    ii r3 = -INFii;

    if(!raio.empty()) {
        r2 = raio.back() + l;
        raio.pop_back();
    }

    if(!raio.empty()) {
        r3 = raio.back() + l;
    }

    ans = max({ans, r1+r2, r2+r3});

    return ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13764 KB Output is correct
2 Correct 46 ms 13684 KB Output is correct
3 Correct 33 ms 10504 KB Output is correct
4 Correct 9 ms 4448 KB Output is correct
5 Correct 7 ms 3788 KB Output is correct
6 Correct 14 ms 5244 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 24 ms 6868 KB Output is correct
9 Correct 31 ms 8912 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 44 ms 10200 KB Output is correct
12 Correct 62 ms 11844 KB Output is correct
13 Correct 3 ms 2892 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2868 KB Output is correct
2 Correct 2 ms 2892 KB Output is correct
3 Incorrect 2 ms 2892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13764 KB Output is correct
2 Correct 46 ms 13684 KB Output is correct
3 Correct 33 ms 10504 KB Output is correct
4 Correct 9 ms 4448 KB Output is correct
5 Correct 7 ms 3788 KB Output is correct
6 Correct 14 ms 5244 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 24 ms 6868 KB Output is correct
9 Correct 31 ms 8912 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 44 ms 10200 KB Output is correct
12 Correct 62 ms 11844 KB Output is correct
13 Correct 3 ms 2892 KB Output is correct
14 Correct 2 ms 2868 KB Output is correct
15 Correct 2 ms 2892 KB Output is correct
16 Incorrect 2 ms 2892 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7108 KB Output is correct
2 Correct 23 ms 7116 KB Output is correct
3 Correct 25 ms 7108 KB Output is correct
4 Correct 25 ms 7140 KB Output is correct
5 Correct 25 ms 7072 KB Output is correct
6 Correct 29 ms 7548 KB Output is correct
7 Correct 30 ms 7244 KB Output is correct
8 Correct 25 ms 7036 KB Output is correct
9 Correct 23 ms 6992 KB Output is correct
10 Correct 28 ms 7248 KB Output is correct
11 Correct 3 ms 2892 KB Output is correct
12 Correct 7 ms 4680 KB Output is correct
13 Correct 7 ms 4680 KB Output is correct
14 Correct 7 ms 4680 KB Output is correct
15 Correct 7 ms 4680 KB Output is correct
16 Correct 8 ms 4640 KB Output is correct
17 Correct 7 ms 4548 KB Output is correct
18 Correct 7 ms 4688 KB Output is correct
19 Correct 7 ms 4680 KB Output is correct
20 Correct 2 ms 2876 KB Output is correct
21 Correct 2 ms 2892 KB Output is correct
22 Correct 2 ms 2876 KB Output is correct
23 Correct 7 ms 4700 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2868 KB Output is correct
2 Correct 2 ms 2892 KB Output is correct
3 Incorrect 2 ms 2892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 13764 KB Output is correct
2 Correct 46 ms 13684 KB Output is correct
3 Correct 33 ms 10504 KB Output is correct
4 Correct 9 ms 4448 KB Output is correct
5 Correct 7 ms 3788 KB Output is correct
6 Correct 14 ms 5244 KB Output is correct
7 Correct 2 ms 2892 KB Output is correct
8 Correct 24 ms 6868 KB Output is correct
9 Correct 31 ms 8912 KB Output is correct
10 Correct 2 ms 2892 KB Output is correct
11 Correct 44 ms 10200 KB Output is correct
12 Correct 62 ms 11844 KB Output is correct
13 Correct 3 ms 2892 KB Output is correct
14 Correct 2 ms 2868 KB Output is correct
15 Correct 2 ms 2892 KB Output is correct
16 Incorrect 2 ms 2892 KB Output isn't correct
17 Halted 0 ms 0 KB -