Submission #1096941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096941		rahidilbayramli	Dreaming (IOI13_dreaming)	C++17	100 / 100	58 ms	30508 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define p_b pop_back
#define f first
#define s second
using namespace std;
const ll sz = 1e5+5, sz2 = 3e5+5;
vector<pll>g[sz];
vector<pll>ng[sz2];
ll vis[sz], vis2[sz], vis3[sz2], dis[sz2], par[sz], dist[sz], maxd = 0, rn1 = -1, rn2 = -1;
void dfs1(ll node)
{
    vis[node] = 1;
    for(auto [u, w] : g[node])
    {
        if(vis[u])
            continue;
        dist[u] = dist[node] + w;
        if(dist[u] > maxd)
        {
            maxd = dist[u];
            rn1 = u;
        }
        dfs1(u);
    }
}
void dfs2(ll node)
{
    vis2[node] = 1;
    for(auto [u, w] : g[node])
    {
        if(vis2[u])
            continue;
        dist[u] = dist[node] + w;
        par[u] = node;
        if(dist[u] > maxd)
        {
            maxd = dist[u];
            rn2 = u;
        }
        dfs2(u);
    }
}
void dfs3(ll node)
{
    vis3[node] = 1;
    for(auto [u, w] : ng[node])
    {
        if(vis3[u])
            continue;
        dis[u] = dis[node] + w;
        if(dis[u] > maxd)
        {
            maxd = dis[u];
            rn1 = u;
        }
        dfs3(u);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(ll i = 0; i < M; i++)
    {
        A[i]++, B[i]++;
        g[A[i]].pb({B[i], T[i]});
        g[B[i]].pb({A[i], T[i]});
    }
    vector<pair<ll, pll>>vect;
    for(ll i = 1; i <= N; i++)
    {
        if(!vis[i])
        {
            rn1 = i;
            rn2 = i;
            maxd = 0;
            dfs1(i);
            dist[rn1] = 0;
            maxd = 0;
            dfs2(rn1);
            vect.pb({maxd, {rn1, rn2}});
        }
    }
    vector<pll>vv;
    for(auto u : vect)
    {
        ll rn1 = u.s.s, maxd = u.f;
        vl v;
        while(par[rn1] != 0)
        {
            v.pb(rn1);
            rn1 = par[rn1];
        }
        ll diff = INT_MAX, sum1 = 0, sum2 = maxd;
        for(auto h : v)
        {
            ll p = abs(dist[h] - maxd);
            if(abs(dist[h] - p) < diff)
            {
                diff = abs(dist[h] - p);
                sum1 = dist[h];
                sum2 = p;
            }
        }
        vv.pb({max(sum1, sum2), min(sum1, sum2)});
    }
    sort(rall(vv));
    ll nval = 0;
    for(auto u : vv)
    {
        ll a = nval + 1, b = nval + 2, c = nval + 3;
        ng[a].pb({b, u.f});
        ng[b].pb({a, u.f});
        ng[b].pb({c, u.s});
        ng[c].pb({b, u.s});
        nval += 3;
    }
    for(ll i = 5; i < nval; i += 3)
    {
        ng[2].pb({i, L});
        ng[i].pb({2, L});
    }
    maxd = 0;
    rn1 = 1, rn2 = 1;
    dfs3(1);
    for(ll i = 1; i <= nval; i++)
        vis3[i] = 0;
    maxd = 0;
    dis[rn1] = 0;
    dfs3(rn1);
    return maxd;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23