Submission #422828

#	Time	Username	Problem	Language	Result	Execution time	Memory
422828		Trickster	Dreaming (IOI13_dreaming)	C++14	0 / 100	41 ms	10052 KiB

dreaming

//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 < n; 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] == 0) 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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23