oj.uz

Submission #718733

# Submission time Handle Problem Language Result Execution time Memory
718733 2023-04-04T15:22:34 Z ovidiush11 Dreaming (IOI13_dreaming) C++14
18 / 100
 39 ms 14416 KB 
#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

#define ll long long
#define ff first
#define ss second
#define mp make_pair

const ll N_ = 1e5+7;

vector<vector<pair<ll,ll>>> a;
vector<ll> maxdistree;
bool st[N_];
pair<ll,ll> disn[N_];

ll maketree(ll p)
{
    st[p] = 1;
    ll x = 0,y = 0;
    for(auto v : a[p])
    {
        if(st[v.ss])continue;
        ll k = maketree(v.ss) + v.ff;
        if(k > x){y = x;x = k;}
        else if(k > y)y = k;
    }
    disn[p].ff = x;
    disn[p].ss = y;
    return x;
}

ll maxtree(ll p,ll k,ll ans)
{
    if(k > ans)return ans;
    k = max(k,disn[p].ss);
    ans = max(disn[p].ff,k);
    ll to = -1;
    for(auto v : a[p])
    {
        if(v.ff + disn[v.ss].ff == disn[p].ff)
        {
            to = v.ss;
            k += v.ff;
            break;
        }
    }
    if(to == -1)return ans;
    return maxtree(to,k,ans);
}

ll solvefor1(ll n)
{
    ll ans = 0;
    for(ll i = 0;i < n;i++)ans = max(ans,disn[i].ff + disn[i].ss);
    return ans;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    a.resize(N);
    for(ll i = 0;i < M;i++)
    {
        a[A[i]].push_back(mp(T[i],B[i]));
        a[B[i]].push_back(mp(T[i],A[i]));
    }
    for(ll i = 0;i < N;i++)st[i] = 0;
    for(ll i = 0;i < N;i++)
    {
        if(!st[i]){
            maketree(i);
            ll x = maxtree(i,0,1e18);
            maxdistree.push_back(x);
        }
    }
    sort(maxdistree.begin(),maxdistree.end(),greater<int>());
    if(maxdistree.size() == 1)return solvefor1(N);
    if(maxdistree.size() == 2)return maxdistree[0] + maxdistree[1] + L;
    return max(solvefor1(N),max(maxdistree[0] + maxdistree[1] + L,maxdistree[2] + maxdistree[1] + 2 * L));
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 14416 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 14416 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 19 ms 7352 KB Output is correct
2 Correct 21 ms 7460 KB Output is correct
3 Correct 21 ms 7436 KB Output is correct
4 Correct 20 ms 7380 KB Output is correct
5 Correct 28 ms 7412 KB Output is correct
6 Correct 23 ms 8280 KB Output is correct
7 Correct 22 ms 7752 KB Output is correct
8 Correct 25 ms 7256 KB Output is correct
9 Correct 21 ms 7344 KB Output is correct
10 Correct 24 ms 7624 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 7 ms 5292 KB Output is correct
13 Correct 6 ms 5452 KB Output is correct
14 Correct 5 ms 5196 KB Output is correct
15 Correct 5 ms 5196 KB Output is correct
16 Correct 5 ms 5196 KB Output is correct
17 Correct 5 ms 5192 KB Output is correct
18 Correct 5 ms 5428 KB Output is correct
19 Correct 5 ms 5196 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 308 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 5 ms 5196 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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