oj.uz

Submission #422837

# Submission time Handle Problem Language Result Execution time Memory
422837 2021-06-10T12:58:51 Z Trickster Dreaming (IOI13_dreaming) C++14
0 / 100
 66 ms 17684 KB 
//Suleyman Atayew

#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
 
#define maxN 200010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) (int)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }

using namespace std;

int n, m, l, mn, mx;
int vis[maxN];
pii F[maxN][5];
vector <pii> E[maxN];

void dfs(int nd, int pr)
{
    vis[nd] = 1;

    for(auto i: E[nd]) {
        int to = i.ff;
        int yol = i.ss;

        if(to != pr) {
            dfs(to, nd);

            if(F[nd][0].ff < F[to][0].ff + yol) {
                F[nd][1] = F[nd][0];
                F[nd][0] = {F[to][0].ff + yol, F[to][0].ss};
            } else if(F[nd][1].ff < F[to][0].ff + yol)
                F[nd][1] = {F[to][0].ff + yol, F[to][0].ss};
        }
    }
}

void dfs2(int nd, int pr, int yol)
{
    if(pr) {
        if(F[nd][0].ss != F[pr][0].ss && F[nd][0].ff < F[pr][0].ff + yol) {
            F[nd][1] = F[nd][0];
            F[nd][0] = {F[pr][0].ff + yol, F[pr][0].ss};
        } else if(F[nd][1].ss != F[pr][0].ss && F[nd][1].ff < F[pr][0].ff + yol)
            F[nd][1] = {F[pr][0].ff + yol, F[pr][0].ss};
    }

    mn = min(mn, F[nd][1].ff);
    mx = max(mx, F[nd][0].ff + F[nd][1].ff);

    for(auto i: E[nd])
        if(i.ff != pr)
            dfs2(i.ff, nd, i.ss);
}


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

    for(int i = 0; i < m; i++) {
        E[A[i]+1].pb({B[i]+1, T[i]});
        E[B[i]+1].pb({A[i]+1, T[i]});
    }

    vector <int> v;
    for(int i = 1; i <= n; i++) {
        if(vis[i]) continue;

        mn = 1e9;
        dfs(i, 0);
        dfs2(i, 0, 0);

        mn = (mn == 1e9 ? 0 : mn);

        v.pb(mn);
    }

    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    return max(max(mx, (v.size() >= 2 ? v[0]+v[1]+L : 0)), (v.size() >= 3 ? v[1]+v[2]+2*L : 0));
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16768 KB Output is correct
2 Correct 64 ms 17684 KB Output is correct
3 Correct 42 ms 15088 KB Output is correct
4 Correct 10 ms 6828 KB Output is correct
5 Correct 13 ms 6220 KB Output is correct
6 Correct 23 ms 7852 KB Output is correct
7 Incorrect 3 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16768 KB Output is correct
2 Correct 64 ms 17684 KB Output is correct
3 Correct 42 ms 15088 KB Output is correct
4 Correct 10 ms 6828 KB Output is correct
5 Correct 13 ms 6220 KB Output is correct
6 Correct 23 ms 7852 KB Output is correct
7 Incorrect 3 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16768 KB Output is correct
2 Correct 64 ms 17684 KB Output is correct
3 Correct 42 ms 15088 KB Output is correct
4 Correct 10 ms 6828 KB Output is correct
5 Correct 13 ms 6220 KB Output is correct
6 Correct 23 ms 7852 KB Output is correct
7 Incorrect 3 ms 4940 KB Output isn't correct
8 Halted 0 ms 0 KB -